算法算法概述详解PPT课件

1、1l 课时数：48节l 上课：1-16周l 成绩：卷面成绩（70%）+平时成绩（30%）l 教材：计算机算法设计与分析, 王晓东,电子工业出版社, 2012l参考书： (1) 算法设计与分析, 郑宗汉, 郑晓明, 清华大学出版社 (2) 算法导论, Thomas H. Cormen编著. 潘金贵等译, 机械工业出版社第1页/共47页22主要内容介绍 第1 1章 算法概述 第2 2章 递归与分治策略 第3 3章 动态规划 第4 4章 贪心算法 第5 5章 回溯法 第6 6章 分支限界法第2页/共47页33意念与现实意念与现实(1): 一个例子一个例子给你一个无限容积的罐子和无限个球，球从1开始连

2、续编号 在差在差1分钟到零点时：将标号为分钟到零点时：将标号为110的的10个球放进罐子，个球放进罐子，然后将然后将10号球从罐子里拿出。号球从罐子里拿出。 在差在差1/2分钟到零点时：将标号为分钟到零点时：将标号为1120的的10个球放进罐个球放进罐子，然后将子，然后将20号球从罐子里拿出。号球从罐子里拿出。 在差在差1/4分钟到零点时：将标号为分钟到零点时：将标号为2130的的10个球放进罐个球放进罐子，然后将子，然后将30号球从罐子里拿出。号球从罐子里拿出。 就这样将游戏进行下去。假定放球和取球不占时间，请问，当时钟指向零点时，罐子里还剩多少个球？第3页/共47页44意念与现实意念与现实

3、(2): 一个例子一个例子这个答案很直接：无穷多个球无穷多个球！所有编号不是10n（n1）的球在放进罐子里后就不会再拿出来；而在到达零点之前这种放球、取球的次数是无限的。因此，罐子里面的球在零点时将是无数个。你很确信这个答案吗？你很确信这个答案吗？ 现在来让我们改变拿球的方式，将每次拿10、20、30号球分别变为拿1、2、3号球，即第x次拿球，所拿出来的球的编号是x。结果又会怎样呢？这个时候，神奇的事情发生了。这个罐子里面的球数将为0。对于任意一个球，设其编号为n，则在差(1/2)n-1分钟到零点时该球将被取出。也就是说，对于任意球n，在零点时它都不在罐子里。因此，零点时罐子里球的个数为0。第

4、4页/共47页55意念与现实意念与现实(3): 一个例子一个例子对于有些人来说，这个答案似乎不可接受。但又确实找不到驳斥的办法。你能找出来吗？也许这个答案是合理的，因为拿球顺序的变化使得算法发生了变化，即我们实际上讨论的是两个算法。可仔细一想又觉得不对，因为两个算法都是每次放进 10 个球，拿出1个球，即从根本上说，这是两个一样的算法，怎么会有截然相反的结果呢?第5页/共47页66意念与现实意念与现实(4): 一个例子一个例子如果我们再次改变试验中拿球的方式，将拿某个特定标号的球改为取出任意标号的球，即在差1分钟到零点时，将标号为110的10个球放进罐子，然后从罐子里任意拿出一个球；在差1/2

5、分钟到零点时，将标号为1120的10个球放进罐子，然后从罐子里任意拿出一个球；在差1/4分钟到零点时，将标号为2130的10个球放进罐子，然后从罐子里任意拿出一个球这种拿球方式又将产生何种结果呢？答案是仍然是答案是仍然是0太不可思议了吧！这三个本质相同的算法三个本质相同的算法怎么有如此匪夷所思的结果呢？如果非要说这三个算法有什么不同，就是拿球时的标号不同。但难道标号的不同使最后球的数量发生了变化?第6页/共47页77意念与现实意念与现实(5): 一个例子一个例子没错，就是这个标号对结果产生了深远影响。从某种意义上说，标号是虚的标号是虚的，它只存在于我们的想象中，但确实对现实结果产生了影响，即我

6、们的思维使算法发生了变化我们的思维使算法发生了变化。或许从另一个角度来看，这个问题就是：没有就是无穷，无穷就是没有。它们之间也许根本没有什么不同，它们的不同只存在于人们的想象或者意念想象或者意念中。也许这是为什么无穷的符号 是由两个0连接而成的，从左右两面看都是无有，而从中间看则是无穷。从这个意义上说，算法是一种思维方式（Algorithmic Thinking），或者说一种哲学。第7页/共47页8一个最简单的算法：1. 起床2. 吃早点3. 上早自习4. 上课5. 吃午饭6. 上课7. 吃晚饭8. 上晚自习9. 睡觉第8页/共47页9第9页/共47页1010第10页/共47页1111第11页

7、/共47页1212算法及其重要性质算法及其重要性质 算法：是指解决问题的一种方法或一个过程。 算法是由若干条指令组成的有穷序列，满足性质： (1)输入：输入：有0个或多个由外部提供的量作为算法的输入。 (2)输出：输出：算法产生至少一个量作为输出。（1个或多个） (3)确定性：确定性：组成算法的每条指令是清晰，无歧义的。 (4)有限性：有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。第12页/共47页1313算法与程序的区别算法与程序的区别 程序是算法用某种程序设计语言的具体程序是算法用某种程序设计语言的具体实现。 程序可以不满足算法的性质程序可以不满足算法的性质(4)

8、。 例如，操作系统是一个在无限循环中执行的程序，因而不是一个算法。 操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。第13页/共47页1414算法的描述方法算法的描述方法第14页/共47页1515第15页/共47页1616第16页/共47页1717第17页/共47页1818第18页/共47页1919第19页/共47页2020第20页/共47页2121第21页/共47页2222第22页/共47页2323第23页/共47页24241.2 算法复杂性分析算法复杂性分析第24页/共47页2525算法复杂性算法复杂性 算法复杂性

9、的高低体现在运行该算法所需要的计算机资源计算机资源的多少的多少上：所需资源越多，算法复杂性越高；反之，所需资源越少，算法复杂性越低。 算法的复杂性有：时间复杂性与空间复杂性 时间复杂性：时间复杂性：算法运行所需要的时间资源量 空间复杂性：空间复杂性：算法运行所需要的空间资源量 选用算法应遵循的一个重要原则重要原则：当给定的问题有多种算法时，选择其中复杂性最低者复杂性最低者 第25页/共47页2626算法复杂性算法复杂性(1) 时间/空间资源的量只依赖于算法要解的问题的规模问题的规模、算算法的输入法的输入和算法本身算法本身的函数。 分别用N、I和A表示算法要解问题的规模、算法的输入和算法本身，而

10、且用C表示复杂性，那么，应该有C=F(N, I, A) 一般把时间复杂性和空间复杂性分开，并分别用T和S来表示，则有：T=T(N, I)和S=S(N, I)。（通常，让A隐含在复杂性函数名当中） 第26页/共47页2727算法复杂性算法复杂性(2)设一台计算机所提供的元运算元运算有k种种，分别记为O1, O2, , Ok同时，设每执行一次执行一次这些元运算所需要时间分别为t1, t2, , tk对于给定的算法A，设用到元运算Oi的次数为ei = ei (N, I), 那么kiiiINetINT1),(),(显然，对于不同的N和I，T(N, I)有多种可能的值。对于给定问题规模，算法A的时间复杂

11、性到底是多少？第27页/共47页2828最好、最坏与平均情况最好、最坏与平均情况最坏情况下的时间复杂性：),(maxmaxINT(N)TNDI),(max1INetkiiiDIN),(*1INetkiii),(*INT最好情况下的时间复杂性：),(minminINT(N)TNDI),(min1INetkiiiDIN),(1INetkiii),(INT平均情况下的时间复杂性：NDIINTIP(N)T),()(avgNDIkiiiINetIP),()(1其中D DN N是规模为N的合法输入的集合合法输入的集合；I*是DN中使T(N, I*)达到Tmax(N)的合法输入.实践表明：可操作性最好且最有

12、实际价值的时间复杂性 是DN中使T(N, )达到Tmin(N)的合法输入；而P(I)是在算法的应用中出现输入I的概率。II第28页/共47页2929第29页/共47页3030第30页/共47页3131第31页/共47页32算法渐近复杂性 设T(N)是算法A的复杂性函数，一般满足：当 N+ ， T(N) +，即 对于T(N)，若存在t(N)，使得当N+， T(N) - t(N) /T(N) 0 ，那么就说t(N)是T(N)的渐近性态，或称为算法A的渐近复杂性。 在数学上， t(N)是T(N)的渐近表达式，是T(N)略去低阶项留下的主项。例如， t(N)比T(N) 简单。2()log1T NNNN

13、2, ()t NNlim()NT N 第32页/共47页3333渐近符号渐近符号算法复杂性在渐近意义下的阶：渐近意义下的记号：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)的阶的阶。 例如： （1）由于对所有的N1有3N4N，则3N=O(N) （2）由于对所有的N1有N+10241025N，则N+1024=O(N) （3）由于对所有的N1有N2 N3 ，则N2=O(

14、N3) （4）由于对所有的N10有2N2+11N-103N2，则2N2+11N-10 =O(N2)第33页/共47页3434渐近符号渐近符号 根据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)； (5) O(Cf(N)=O(f(N)，其中C是一个正的常数； (6) f=O(f)。 第34页/共47页3535渐近符号渐近符号 的定义的定义：如果存在正的常数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充分大时