算法分析技术概要概要课件
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 =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*
2、log(n) n + 1,4,Solving summations : Binary insertion sort,由于二分查找最后要定位点在的一个具体的点上,而且这个点必须是刚好必要插入的小的,所以必然是要使左指针与右指针相互移过,故每插入一个,需要比较的次数为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). Prove: 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
3、+ 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 dividing 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
《算法分析技术概要概要课件》由会员F****n分享,可在线阅读,更多相关《算法分析技术概要概要课件》请在金锄头文库上搜索。
2024-04-18 25页
2024-04-18 29页
2024-04-18 38页
2024-04-18 16页
2024-04-09 21页
2024-04-09 26页
2024-04-09 28页
2024-04-09 19页
2024-04-09 26页
2024-04-09 23页