计算机算法设计与分析

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