《算法引论》PPT课件.ppt

南京理工大学,算法设计与分析Algorithm Design and Analysis,孙廷凯,南京理工大学,课程内容(32学时),常用的算法设计策略(包括分治策略、动态规划、贪心策略、回溯法、随机算法等)算法复杂度分析方法(计算迭代次数、使用递归方程、频度分析等),南京理工大学,课程要求,掌握常用的算法设计策略、算法复杂度分析方法授课方式：讲授考核方式：,南京理工大学,教材,算法设计技巧与分析，M.H.Alsuwaiyel著,电子工业出版社，吴伟昶等译，2004,南京理工大学,相关参考文献,Algorithm Design Techniques and Analysis,M.H.Alsuwaiyel.(影印本).电子工业出版社.2003算法导论(第2版)，Thomas H.Cormen等著，潘金贵等译，机械工业出版社，2006.计算机算法设计与分析(第3版),王晓东,电子工业出版社,2007.算法设计与分析，王红梅编著，清华大学出版社，2006.,南京理工大学,1 算法引论,历史背景算法复杂度与渐近分析方法如何估计算法的复杂度算法复杂度分析的意义,南京理工大学,历史背景,阶段1：二十世纪30年代，能否使用一个有效的过程来求解一个问题(相当于现在算法的概念)一直是人们所关注的。当时的焦点是将问题进行分类：可解或是不可解。关注问题是否可以求解的领域称为可计算理论(computability theory or theory of computation)。出现了一系列的计算模型，例如：calculus of Church、Post machines of Post、Turing machines of Turing、RAM model of computation。阶段2：随着数字计算机的出现，人们越来越关注于那些可求解的问题。一开始，人们满足于能够在一定的时间内解决一个特定的问题，而不去关注所需要的资源。慢慢地，人们需要考虑在有限资源的条件下高效地解决问题。这就导致了计算复杂度(computational complexity)这一新学科的诞生。在这个领域，主要是研究解决可求解问题时所需要的资源，主要是时间和空间复杂性。有时候，其他的资源也需要考虑，例如，通信代价、需要使用的处理器的个数(使用并行计算模型)等等。,南京理工大学,引例：搜索问题,给定已经排好序(不妨假设为非降序)的n个元素A1n,现在要判定一个给定的元素x是否在此数组中出现。方法1：顺序搜索方法2：二分搜索,南京理工大学,二分搜索算法,输入：非降序排列的数组A1n和元素x输出：如果x=Aj,1 j n,则输出j,否则输出0.1.low1;high n;j02.while(low high)and(j=0)3.mid(low+high)/24.if x=Amid then j mid5.else if xAmid then high mid-16.else low mid+17.end while8.return j,南京理工大学,分析,最好情形：比较1次,最坏情形：比较logn+1次每次循环都要抛弃一些元素，例如第二次循环时，剩余元素为A1mid-1或Amid+1n，不妨设为Amid+1n，则剩余的元素个数是n/2第j次while循环时，剩余元素的个数是n/2j-1或者找到x，或者程序在子序列长度达到1时终止搜索,此时n/2j-1=1 1 n/2j-1 2 2j-1 n 2j lognjlogn+1j=logn+1,南京理工大学,算法及其性质,算法是对问题求解过程的准确描述，由有限条指令组成，这些指令能在有限时间内执行完毕并产生确定性的输出。算法需满足的4个性质：输入：零个或多个外部量作为输入。输出：至少产生一个量作为输出,它(们)与输入量之间存在某种特定的联系。确定性：组成算法的每条指令都是清晰、无歧义的。有限性：每条指令的执行次数有限，执行每条指令的时间也有限。程序与算法的区别：程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的有限性性质。,南京理工大学,算法的复杂度,复杂度：算法运行时需要耗费计算机资源的量，可以分为时间复杂度和空间复杂度。算法复杂度依赖于三个方面：待求解问题的规模、算法的输入和算法本身。用n,I,A分别表示问题的规模、算法的输入和算法本身，用表示C复杂度，则有：C=F(n,I,A)。如果将时间复杂度和空间复杂度分开，则有T=T(n,I,A)和S=S(n,I,A)。通常，我们让A隐藏在复杂度函数名中，所以有T=T(n,I)和S=S(n,I)。由于时间复杂度和空间复杂度概念类似，计量方法类似，且空间复杂度分析相对简单，因此本课程主要讨论算法的时间复杂度。,南京理工大学,T=T(n,I)的具体化,假设计算机提供k 种元运算，分别记为O1,O2,Ok。所谓元运算指的是这样一类运算：不管使用什么样的算法和输入数据，该运算的上阶是一个常数时间(关于阶，参见后文描述)。例如，算术运算、比较、逻辑、赋值等。元运算Oi每执行一次需要的时间为ti。对于给定的算法A，已经知道用到的元运算Oi 的执行次数为ei,i=1,.,k。很显然ei是n 和I 的函数，即ei=ei(n,I)。至此，就有：,南京理工大学,分析,T(n,I)给出的是在问题规模为n，输入为I 时的时间复杂度。但是我们不可能，也没必要对每种可能的输入都去求其时间复杂度。通常可以考虑3 种情形下的时间复杂度：最坏情形、最好情形以及平均情形。,实践表明：可操作性最强、最有实际价值的是算法最坏情形下的时间复杂度。,南京理工大学,使用算法的绝对运行时间来度量其时间复杂度？NO,一个编程实现了的算法的具体运行时间，不仅仅和算法本身相关，还和很多其他因素密切相关：机器性能、编程语言、编译器、编程技巧等等。在分析一个算法的运行时间时，通常将该算法和其他算法在同一问题、甚至是不同的问题上进行比较，因而运行时间只能是相对的，而不是绝对的。希望算法的描述不仅独立于机器，并且可以以任何语言来加以描述，包括自然语言。希望使用度量算法运行时间的准则不依赖于技术的进步。不仅仅关注小规模输入下的，而且还关注在大规模输入下的情形。,南京理工大学,渐近分析(Asymptotic Analysis),对于T(n)，当n单调递增并趋于 时，T(n)也是单调增加并趋于。为此,如果存在一个T*(n)，使得当n 时有(T(n)T*(n)/T(n)0,就称T*(n)是T(n)当n 的渐近性态，或称T*(n)是给定算法在n 时的渐近复杂度。显然,T*(n)不是唯一的。我们可以尽可能的选择简单的T*(n)，然后使用T*(n)来替代T(n)作为n 的复杂度度量。渐近复杂度分析只要关心T*(n)的阶就可以了(在n 充分大时)，不必关心其中的常数因子。,南京理工大学,4种阶：O,和o,假设：f(n)和g(n)是定义在正数集上的正函数。(此假设的实际意义?)定义1(O)：如果存在正的常数C和自然数n0，使得当nn0时，有f(n)Cg(n)，则称函数f(n)在n 充分大时有上有界，且g(n)是它的一个上界，记做f(n)=O(g(n)，并称f(n)的阶不高于g(n)的阶。,南京理工大学,例子,例：f(n)n2，g(n)n3。因为：存在n0 1，C=1，当n n0时，有n2Cn3,所以：n2=O(n3)例：f(n)n2，g(n)n2。因为：存在n0 1，C=1,n n0时，有n2Cn2,所以：n2=O(n2)例：f(n)n2+nlog(n)，g(n)n2。同样有n2+nlog(n)=O(n2)例：f(n)an2+nlog(n)，g(n)n2。同样有an2+nlog(n)=O(n2)例：f(n)an2+nlog(n)+c，g(n)n2。同样有an2+nlog(n)+c=O(n2),南京理工大学,小结,在进行阶的运算时，常系数、低的阶以及常数项可以忽略。根据O的定义，得到的是在问题规模充分大时，算法复杂度的一个上界。上界的阶越低则评估越有价值。运算规则O(f)+O(g)=O(max(f,g);O(f)O(g)=O(fg);O(Cf(n)=O(f(n);f=O(f);,南京理工大学,定义2()：如果存在正的常数C 和自然数n0，使得当n n0时，有f(n)Cg(n)，则称函数f(n)在n 充分大时有下有界，且g(n)是它的一个下界，记做f(n)=(g(n)，并称f(n)的阶不低于g(n)的阶。下界的阶越高，则评估精度越高，也就越有价值。,南京理工大学,和o,定义3()：f(n)=(g(n)，当且仅当f(n)=O(g(n)，且f(n)=(g(n)，称f(n)和g(n)是同阶。定义4(o)：对于任意给定的 0，存在正整数n0，使得当n n0 时，有f(n)/g(n)，则称函数f(n)在n 充分大时的阶比g(n)低，记为f(n)=o(g(n)。,南京理工大学,小结,进行算法的时间复杂度分析，就是求其T(n)，并用O、或是以尽可能简单的形式进行表示。理想情况下，希望能够使用表示算法的时间复杂性。退而求其次，可以使用O或是。使用O时，希望估计的上界的阶越小越好。使用时，希望估计的下界的阶越大越好。,南京理工大学,算法耗费时间随问题规模的变化,南京理工大学,阶运算的几个实例,=,(1),=,解：因为,所以,(2),解:a.因为,有,=,b.又因为,则有,命题成立,南京理工大学,(3),解:因为,(不准确),a.,b.,所以,换底公式,所以,亦即,1,2,n,1,2,n+1,南京理工大学,(4),x,南京理工大学,估计算法的时间复杂度,计算迭代次数使用递归方程频度分析,南京理工大学,计算迭代次数,通常，程序的运行时间和程序的迭代次数成比例。因此计算程序的迭代次数就可以作为算法运行时间的指示器。这在很多算法中都可以得到应用，如查找、排序等等。,南京理工大学,计算迭代次数,输入：n(n=2k，k 为某一正整数)输出：count1.count 0 2.while n 1 3.for j 1 to n4.count count+1/执行一次耗费时间设为a5.end for6.n n/2/执行一次耗费时间设为d 7.end while8.return count,分析：while 迭代的次数是k+1次(因为n1 可以写成n20,运行过程n=2k20)，k=log n。在每次while 循环里面for 依次执行n，n/2,n/4,1 次，所以，算法的时间复杂度为：,南京理工大学,思考？,为什么在上面计算算法的时间复杂度时不考虑step 6,而只是考虑step 4呢？如果同时考虑 step 4和step 6，我们有：,小结：使用计算迭代次数的技术来分析算法的时间复杂度时，只需要考虑最深层次的迭代。,南京理工大学,例：,输入：正整数n输出：step 5 的执行次数1.count 02.for i 1 to n3.m n/i4.for j 1 to m5.count count+16.end for7.end for8.return count,分析：Step5 的执行次数依次为：n,n/2,n/3,n/n,因为,所以,南京理工大学,2 使用递归方程,输入：非降序排列的数组A1n和元素x输出：如果x=Aj,1 j n,则输出j,否则输出0.1.low1;high n;j02.while(low high)and(j=0)3.mid(low+high)/24.if x=Amid then j mid5.else if xAmid then high mid-16.else low mid+17.end while8.return j,南京理工大学,3 频度分析,对于有些算法，要像前面那样准确地分析算法的运行时间非常麻烦，有时甚至是不可能的。这时候，可以使用频度分析，我们将在后续章节中进行讲解。(单源最短路径、Prim 算法等等),南京理工大学,算法复杂度分析的意义,已知待求解问题的多种算法时，挑选复杂度尽可能低的算法进行应用。给定待求解的问题，设计复杂度尽可能低的算法。设计出算法后，不要急于实现，而是先进行复杂度分析后；若该算法确实可行，才有实现的价值与必要。,南京理工大学,研究算法还有必要么？,随着计算机设计和制造技术的突飞猛进，计算机的计算速度和存储容量在不断增长。有的人因此认为不必要再去苦苦追求高效率的算法。认为低效的算法可以由高速的计算机来弥补，认为在可接受的一定时间内用低效的算法完不成的任务，只要移植到高速的计算机上就能完成。造成上述错误认识的原因是他们没看到：随着经济的发展、社会的进步、科学研究的深入，要求计算机解决的问题越来越复杂、规模越来越大，也呈增长之势；而问题复杂程度和规模的线性增长导致的时耗的增长和空间需求的增长，对低效算法来说，都是非线性的，决非计算机速度和容量的线性增长带来的时耗减少和存储空间的扩大所能抵销。,南京理工大学,几点说明,“低阶复杂度的算法比高阶复杂度的算法效率高”这个结论，只是在问题的规模充分大时才成立。复杂度分别为n3与10n2：当n10时，n310n2;而n10时，n310n2，即复杂度为n3的算法更有效。在问题规模较小时，我们往往并不一味追求低复杂度的算法，而是更侧重于算法的简单性。当两个算法的渐近复杂度的阶相同时，必须进一步综合考察渐近复杂度表达式中的低阶及常数因子才能判别它们的优劣。例如：复杂度为n1ogn/l00 的算法显然比复杂度为l00n1ogn 的算法来得有效。,