《算法分析技术》由会员分享，可在线阅读，更多相关《算法分析技术（36页珍藏版）》请在金锄头文库上搜索。
1、算法分析技术概要,2007/06/1,2,算法分析技术,求和技术 Solving summations 递归（分治）算法 Solving recurrence 估计与归纳证明法 The substitution method 递归树展开法 The recursion-tree method The master method 快速排序算法及复杂度分析 其他排序算法,3,求和技术 Solving summations ： Shifting method binary insertion sort,for i = 1 to n biInsert( Ai, S);,S:,Sn=ki=1 i*2i-1
2、 =1*20+2*21+3*22+4*23 +(i-1)*2i-2+i*2i-1+(i+1)*2i+k*2k-1,2*Sn=k i=1 i*2i-1*2=k i=1 i*2i = 1*21+2*22+3*23+ +(i-2)*2i-2 +(i-1)*2i-1+i*2i+1+(k-1)*2k-1+k*2k,Sn = k*2k - k i=2 2i-1 + 1 = k*2k - 2k + 1 = n*log(n) n + 1,4,Solving summations ： Binary insertion sort,由于二分查找最后要定位点在的一个具体的点上，而且这个点必须是刚好必要插入的小的，所以
3、必然是要使左指针与右指针相互移过，故每插入一个，需要比较的次数为log2n。一共需要比较log2n， log2n1时，实际上，在n10时已经是很好的近似了） 所以 nlog2n-n = log2n= nlog2n, 故二分法在比较的时间复杂度： T(n) = O(nlog2n),张浩炜提供,5,Solving recurrence (chapter 4) The substitution method (4.1),Merge sort:,(the base cases),6,The substitution method (cont.),Guess: T (n) = O(n lg n). Pr
4、ove: T (n) c nlg n (for a constant c 0.),T(n) 2(c n/2lg(n/2) + n cn lg(n/2) + n = cn lg n - cn lg 2 + n = cn lg n - cn + n cn lg n,7,The recursion-tree method (4.2),The recursion tree for T (n) = 3T (n/4) + cn2, Drawing out a recursion tree is a straightforward way to devise a good guess.,Cost of di
5、viding problem & combination,8,The recursion tree for T (n) = 3T (n/4) + cn2,3log4n,Base cases,9,The master method (4.3),f(n) nlogba T(n) = (nlogba) f(n) =(nlogba) T(n) = (nlogba lgn) f(n) nlogba T(n) = (f(n),T(n) =,10,11,Application of Master-theorem,12,Application of Master-theorem (cont.),13,Appl
6、ication of Master-theorem (cont.),14,Application of Master-theorem (cont.),15,Compute Fibonacci numbers,16,Compute Fibonacci numbers,17,关于上次课的作业,冒泡法排序可以考虑通过一个increase变量替代重复的循环结构。最好能有“没有交换就停止”的策略。 重排数组作业，设置头尾指针，交换正负，直到头=尾 算法分析：注意区别最坏情况和平均情况的计算方法。 参考教材 p248的等概率情况下的算法代价分析。,18,Quicksort （chapter 7）,19,Q
7、uicksort (cont.),Divide: Partition (rearrange) the array Ap r into two subarrays Ap q - 1 and Aq + 1 r such that： each element of Ap q - 1 Aq Conquer: Sort the two subarrays Ap q -1 and Aq +1 r by recursive calls to quicksort. Combine: Since the subarrays are sorted in place, no work is needed to co
8、mbine them: the entire array Ap r is now sorted.,20,Quicksort (cont.),O(n),?,21,Quicksort (cont.),22,Quicksort (cont.),23,Quicksort (cont.),24,Quicksort (cont.),25,Quicksort (cont.),26,Lower bounds for sorting （8.1）,27,The decision-tree model,4=6,28,The decision-tree model(cont.),29,30,31,Counting s
9、ort （8.2）,32,COUNTING-SORT(A, B, k),1 (for i 0 to k) do Ci 0 /initialize Ci 2 (for j 1 to lengthA ) do CAj CAj + 1 /Ci now contains the number of elements equal to i. 3 (for i 1 to k) do Ci Ci + Ci - 1 /Ci now contains the number of elements less than or equal to i. 4 (for j lengthA downto 1) do BCA
10、j Aj ; /CAj store the rank of Aj CAj CAj - 1 ; ,33,Example of counting sort,34,35,36,Home work （不用提交，可以相互讨论）,Exercises 4.3-1 Use the master method to give tight asymptotic bounds for the following recurrences. T (n) = 4T(n/2) + n. T (n) = 4T(n/2) + n2. T (n) = 4T(n/2) + n3 Exercises 4.3-2 The recurrence T(n) = 7T (n/2)+n2 describes the running time of an algorithm A. A competing algorithm A has a running time of T(n) = aT(n/4) + n2. What is the largest integer value for a such that A is asymptotically faster than A? 28号下午考试。,
