《算法第1章算法概述详解》由会员分享，可在线阅读，更多相关《算法第1章算法概述详解（47页珍藏版）》请在金锄头文库上搜索。
1、计算机算法设计与分析计算机算法设计与分析计算机算法设计与分析主讲人：袁运浩E-mail: 计算机科学与技术系江南大学物联网工程学院1计算机算法设计与分析l 课时数：课时数：48节l 上课：上课：1-16周l 成绩：成绩：卷面成绩（70%）+平时成绩（30%）l 教材：教材：计算机算法设计与分析, 王晓东,电子工业出版社, 2012l参考书：参考书： (1) 算法设计与分析, 郑宗汉, 郑晓明, 清华大学出版社 (2) 算法导论, Thomas H. Cormen编著. 潘金贵等译, 机械工业出版社2计算机算法设计与分析3主要内容介绍第第1 1章章算法概述算法概述第第2 2章章递归与分治策略递归
2、与分治策略第第3 3章章动态规划动态规划第第4 4章章贪心算法贪心算法第第5 5章章回溯法回溯法第第6 6章章分支限界法分支限界法3计算机算法设计与分析4意念与现实意念与现实(1): 一个例子一个例子给你一个无限容积的罐子和无限个球，球从1开始连续编号 在在差差1分分钟钟到到零零点点时时：将将标标号号为为110的的10个个球球放放进进罐罐子子，然后将然后将10号球从罐子里拿出。号球从罐子里拿出。 在在差差1/2分分钟钟到到零零点点时时：将将标标号号为为1120的的10个个球球放放进进罐罐子，然后将子，然后将20号球从罐子里拿出。号球从罐子里拿出。 在在差差1/4分分钟钟到到零零点点时时：将将标
3、标号号为为2130的的10个个球球放放进进罐罐子，然后将子，然后将30号球从罐子里拿出。号球从罐子里拿出。 就这样将游戏进行下去。假定放球和取球不占时间，请问，当时钟指向零点时，罐子里还剩多少个球？4计算机算法设计与分析5意念与现实意念与现实(2): 一个例子一个例子这个答案很直接：无无穷穷多多个个球球！所有编号不是10n（n1）的球在放进罐子里后就不会再拿出来；而在到达零点之前这种放球、取球的次数是无限的。因此，罐子里面的球在零点时将是无数个。你很确信这个答案吗？你很确信这个答案吗？ 现在来让我们改变拿球的方式，将每次拿10、20、30号球分别变为拿1、2、3号球，即第x次拿球，所拿出来的球
4、的编号是x。结果又会怎样呢？这个时候，神奇的事情发生了。这个罐子里面的球数将为0。对于任意一个球，设其编号为n，则在差(1/2)n-1分钟到零点时该球将被取出。也就是说，对于任意球n，在零点时它都不在罐子里。因此，零点时罐子里球的个数为0。5计算机算法设计与分析6意念与现实意念与现实(3): 一个例子一个例子对于有些人来说，这个答案似乎不可接受。但又确实找不到驳斥的办法。你能找出来吗？也许这个答案是合理的，因为拿球顺序的变化使得算法发生了变化，即我们实际上讨论的是两个算法。可仔细一想又觉得不对，因为两个算法都是每次放进 10 个球，拿出1个球，即从根本上说，这是两个一样的算法，怎么会有截然相反
5、的结果呢?6计算机算法设计与分析7意念与现实意念与现实(4): 一个例子一个例子如果我们再次改变试验中拿球的方式，将拿某个特定标号的球改为取出任意标号的球，即在差1分钟到零点时，将标号为110的10个球放进罐子，然后从罐子里任意拿出一个球；在差1/2分钟到零点时，将标号为1120的10个球放进罐子，然后从罐子里任意拿出一个球；在差1/4分钟到零点时，将标号为2130的10个球放进罐子，然后从罐子里任意拿出一个球这种拿球方式又将产生何种结果呢？答案是仍然是答案是仍然是0太不可思议了吧！这三三个个本本质质相相同同的的算算法法怎么有如此匪夷所思的结果呢？如果非要说这三个算法有什么不同，就是拿球时的标
6、号不同。但难道标号的不同使最后球的数量发生了变化?7计算机算法设计与分析8意念与现实意念与现实(5): 一个例子一个例子没错，就是这个标号对结果产生了深远影响。从某种意义上说，标标号号是是虚虚的的，它只存在于我们的想象中，但确实对现实结果产生了影响，即我我们们的的思思维维使使算算法法发发生生了了变变化化。或许从另一个角度来看，这个问题就是：没有就是无穷，无穷就是没有。它们之间也许根本没有什么不同，它们的不同只存在于人们的想想象象或或者者意意念念中。也许这是为什么无穷的符号 是由两个0连接而成的，从左右两面看都是无有，而从中间看则是无穷。从这个意义上说，算法是一种思维方式（算法是一种思维方式（A
7、lgorithmic Thinking），或者说一种哲学），或者说一种哲学。8计算机算法设计与分析一个最简单的算法一个最简单的算法：1. 起床2. 吃早点3. 上早自习4. 上课5. 吃午饭6. 上课7. 吃晚饭8. 上晚自习9. 睡觉9计算机算法设计与分析10计算机算法设计与分析1111计算机算法设计与分析1212计算机算法设计与分析131.1.2 算法及其重要性质算法及其重要性质 算法：是指解决问题的一种方法或一个过程。 算法是由若干条指令组成的有穷序列，满足性质： (1)输入：输入：有0个或多个由外部提供的量作为算法的输入。 (2)输出：输出：算法产生至少一个量作为输出。（1个或多个）
8、(3)确定性：确定性：组成算法的每条指令是清晰，无歧义的。 (4)有有限限性性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。13计算机算法设计与分析14算法与程序的区别算法与程序的区别 程序是算法用某种程序设计语言的具体程序是算法用某种程序设计语言的具体实现。 程序可以不满足算法的性质程序可以不满足算法的性质(4)。 例如，操作系统是一个在无限循环中执行的程序，因而不是一个算法。 操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。14计算机算法设计与分析151.1.3 算法的描述方法算法的描述方法15
9、计算机算法设计与分析1616计算机算法设计与分析1717计算机算法设计与分析1818计算机算法设计与分析1919计算机算法设计与分析2020计算机算法设计与分析2121计算机算法设计与分析2222计算机算法设计与分析2323计算机算法设计与分析2424计算机算法设计与分析251.2 算法复杂性分析算法复杂性分析25计算机算法设计与分析26算法复杂性算法复杂性 算法复杂性的高低体现在运行该算法所需要的计计算算机机资资源源的的多多少少上：所需资源越多，算法复杂性越高；反之，所需资源越少，算法复杂性越低。 算法的复杂性有：时间复杂性与空间复杂性 时间复杂性：时间复杂性：算法运行所需要的时间资源量 空
10、间复杂性：空间复杂性：算法运行所需要的空间资源量 选用算法应遵循的一个重重要要原原则则：当给定的问题有多种算法时，选择其中复杂性最低者复杂性最低者 26计算机算法设计与分析27算法复杂性算法复杂性(1) 时间/空间资源的量只依赖于算法要解的问问题题的的规规模模、算算法的输入法的输入和算法本身算法本身的函数。 分别用N、I和A表示算法要解问题的规模、算法的输入和算法本身，而且用C表示复杂性，那么，应该有C=F(N, I, A) 一般把时间复杂性和空间复杂性分开，并分别用T和S来表示，则有：T=T(N, I)和S=S(N, I)。（通常，让A隐含在复杂性函数名当中） 27计算机算法设计与分析28算
11、法复杂性算法复杂性(2)设一台计算机所提供的元运算元运算有k种种，分别记为O1, O2, , Ok同时，设每执行一次执行一次这些元运算所需要时间分别为t1, t2, , tk对于给定的算法A，设用到元运算Oi的次数为ei = ei (N, I), 那么显然，对于不同的显然，对于不同的N和和I，T(N, I)有多种可能的值。有多种可能的值。对于给定问题规模，算法对于给定问题规模，算法A的时间复杂性的时间复杂性到底是多到底是多少？少？28计算机算法设计与分析291.2.1 最好、最坏与平均情况最好、最坏与平均情况最坏情况下的时间复杂性：最好情况下的时间复杂性：平均情况下的时间复杂性：其中D DN
12、N是规模为N的合法输入的集合合法输入的集合；I*是DN中使T(N, I*)达到Tmax(N)的合法输入.实践表明：可操实践表明：可操作性最好且最有作性最好且最有实际价值的时间实际价值的时间复杂性复杂性 是DN中使T(N, )达到Tmin(N)的合法输入；而P(I)是在算法的应用中出现输入I的概率。29计算机算法设计与分析3030计算机算法设计与分析3131计算机算法设计与分析3232计算机算法设计与分析算法渐近复杂性算法渐近复杂性设T(N)是算法A的复杂性函数，一般满足：当 N+ ， T(N) +，即 对于T(N)，若存在t(N)，使得当N+， T(N) - t(N) /T(N) 0 ，那么就
13、说t(N)是T(N)的渐近性态渐近性态，或称为算法A的渐近渐近复杂性复杂性。在数学上， t(N)是T(N)的渐近表达式渐近表达式，是是T(N)略去低阶项留下略去低阶项留下的主项的主项。例如， t(N)比T(N) 简单。33计算机算法设计与分析341.2.2 渐近符号渐近符号算法复杂性在渐近意义下的阶：渐近意义下的记号：O、o 设f(N)和g(N)是定义在正数集上的正函数正函数。 O的定义的定义：如果存在正的常数C和自然数N0，使得当NN0时有f(N)Cg(N)，则称函数f(N)当N充分大时有上界，且g(N)是它的一个上界上界，记为f(N)=O(g(N)。即f(N)的阶不高于的阶不高于g(N)的
14、阶的阶。 例如： （1）由于对所有的N1有3N4N，则3N=O(N) （2）由于对所有的N1有N+10241025N，则N+1024=O(N) （3）由于对所有的N1有N2 N3 ，则N2=O(N3) （4）由于对所有的N10有2N2+11N-103N2，则2N2+11N-10 =O(N2)34计算机算法设计与分析351.2.2 渐近符号渐近符号 根据O的定义，容易证明它有如下运算规则： (1) O(f)+O(g)=O(max(f, g)； (2) O(f)+O(g)=O(f+g)； (3) O(f)O(g)=O(fg)； (4) 如果g(N)=O(f(N)，则O(f)+O(g)=O(f)；
15、(5) O(Cf(N)=O(f(N)，其中C是一个正的常数； (6) f=O(f)。 35计算机算法设计与分析361.2.2 渐近符号渐近符号 的定义的定义：如果存在正的常数C和自然数N0，使得当NN0时有f(N)Cg(N)，则称函数f(N)当N充分大时下有界，且g(N)是它的一个下界下界，记为f(N)=(g(N)。即f(N)的阶不低的阶不低于于g(N)的阶的阶。 的定义的定义：定义f(N)=(g(N) 当且仅当f(N)=O(g(N)且f(N)= (g(N)。此时称f(N)与g(N)同阶同阶。 o o的定义的定义：对于任意任意给定的0，都存在正整数N0，使得当NN0时有f(N)/g(N),则称函数f(N)当当N充分大时的阶比充分大时的阶比g(N)低低，记为f(N)=o(g(N)。 例如，4NlogN+7=o(3N2+4NlogN+7)。 36计算机算法设计与分析3737计算机算法设计与分析3838计算机算法设计与分析3939计算机算法设计与分析4040计算机算法设计与分析4141计算机算法设计与分析4242计算机算法设计与分析4343计算机算法设计与分析4444计算机算法设计与分析4545计算机算法设计与分析4646计算机算法设计与分析4747
