算法引论课件.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个元素A[1…n] ,现在要判定一个给定的元素x是否在此数组中出现–方法1：顺序搜索–方法2：二分搜索算法引论二分搜索算法输入：非降序排列的数组A[1…n]和元素x输出：如果x=A[j], 1 j n,则输出j,否则输出0.1. low←1; high ←n; j←02. while(low high) and (j=0)3. mid ← ( low+high)/24. if x=A[mid] then j ←mid5. else if x

•算法需满足的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，使得当n≥n0时， 有f(n)≤C·g(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时，有n2≤Cn3 , 所以：n2 = O(n3) •例： f(n)＝ n2 ，g(n)＝ n2因为：存在n0 ＝1，C=1, n≥ n0时，有n2≤Cn2 , 所以：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( f·g);–O(C·f (n)) = O(f (n));–f = O( f ); 算法引论Ω•定义2(Ω)： 如果存在正的常数C 和自然数n0 ， 使得当n ≥ n0时， 有f(n)≥C·g(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时，希望估计的上界的阶越小越好•使用Ω时，希望估计的下界的阶越大越好算法引论算法耗费时间随问题规模的变化Algorithm1234 5Time function(ms)33n46n lg n13n23.4n32nInput size(n)Solution time100.00033 sec.0.0015 sec.0.0013 sec.0.0034 sec.0.001 sec.1000.0033 sec.0.03 sec.0.13 sec.3.4 sec.41016 yr.1,0000.033 sec.0.45 sec.13 sec.0.94 hr.10,0000.33 sec.6.1 sec.22 min.39 days100,0003.3 sec.1.3 min.1.5 days108 yr.Time allowedMaximum solvable input size (approx.)1 second30,0002,00028067201 minute1,800,00082,0002,20026026算法引论阶运算的几个实例= (1)= 解：因为所以(2)解: a. 因为有= b.又因为则有命题成立算法引论(3)解: 因为(不准确)a. b. 所以 换底公式 所以 亦即 1 2n1 2n+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次(因为n≥1 可以写成n≥20, 运行过程n=2k→20)，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/i4. for j ← 1 to m5. count ← count+16. end for7. end for8. return count分析：Step5 的执行次数依次为： n, n/2, n/3, …, n/n因为所以算法引论2 使用递归方程 输入：非降序排列的数组A[1…n]和元素x输出：如果x=A[j], 1 j n,则输出j,否则输出0.1. low←1; high ←n; j←02. while(low high) and (j=0)3. mid ← ( low+high)/24. if x=A[mid] then j ←mid5. else if x

这时候，可以使用频度分析，我们将在后续章节中进行讲解单源最短路径、Prim 算法等等)算法引论算法复杂度分析的意义 •已知待求解问题的多种算法时，挑选复杂度尽可能低的算法进行应用•给定待求解的问题，设计复杂度尽可能低的算法•设计出算法后，不要急于实现，而是先进行复杂度分析后；若该算法确实可行，才有实现的价值与必要算法引论研究算法还有必要么？•随着计算机设计和制造技术的突飞猛进，计算机的计算速度和存储容量在不断增长有的人因此认为不必要再去苦苦追求高效率的算法认为低效的算法可以由高速的计算机来弥补，认为在可接受的一定时间内用低效的算法完不成的任务，只要移植到高速的计算机上就能完成 •造成上述错误认识的原因是他们没看到：随着经济的发展、社会的进步、科学研究的深入，要求计算机解决的问题越来越复杂、规模越来越大，也呈增长之势；而问题复杂程度和规模的线性增长导致的时耗的增长和空间需求的增长，对低效算法来说，都是非线性的，决非计算机速度和容量的线性增长带来的时耗减少和存储空间的扩大所能抵销算法引论几点说明•“低阶复杂度的算法比高阶复杂度的算法效率高”这个结论，只是在问题的规模充分大时才成立–复杂度分别为n3与10n2：当n>10时，n3>10n2; 而n<10时，n3<10n2，即复杂度为n3的算法更有效。

•在问题规模较小时，我们往往并不一味追求低复杂度的算法，而是更侧重于算法的简单性•当两个算法的渐近复杂度的阶相同时，必须进一步综合考察渐近复杂度表达式中的低阶及常数因子才能判别它们的优劣–例如：复杂度为n1ogn/l00 的算法显然比复杂度为l00n1ogn 的算法来得有效算法引论。