算法分析技术概要概要.ppt

《算法分析技术概要概要.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法分析技术概要2007/06/1算法分析技术求和技术Solvingsummations递归（分治）算法Solvingrecurrence估计与归纳证明法Thesubstitutionmethod递归树展开法Therecursion-treemethodThemastermethod快速排序算法及复杂度分析其他排序算法2求和技术Solvingsummations：Shiftingmethod——binaryinsertionsortfori=1tonbiInsert(A[i],S);S:Sn=∑ki=1i*2i-1=1*20+2*21+3*22+4*23....

2、+(i-1)*2i-2+i*2i-1+(i+1)*2i+…+k*2k-12*Sn=∑ki=1i*2i-1*2=∑ki=1i*2i=1*21+2*22+3*23+....+(i-2)*2i-2+(i-1)*2i-1+i*2i+1+…+(k-1)*2k-1+k*2kSn=k*2k-∑ki=22i-1+1=k*2k-2k+1=n*log(n)–n+13Solvingsummations：Binaryinsertionsort由于二分查找最后要定位点在的一个具体的点上，而且这个点必须是刚好必要插入的小的，所以必然是要使左指针与右指针相互移过，故每插入一个，需要比较的次数

3、为「log2n」。一共需要比较Σ「log2n」，log2n<=⌊log2n」<=log2n+1,∑log2n<=∑⌊log2n」<=∑(log2n+1),由斯特林（Stirling）公式得∑log2n=log2n！=nlog2n-n;（当n>>1时，实际上，在n>10时已经是很好的近似了）所以nlog2n-n<=∑⌊log2n」<=nlog2n,故二分法在比较的时间复杂度：T(n)=O(nlog2n)张浩炜提供4Solvingrecurrence(chapter4)——Thesubstitutionmethod(4.1)Mergesort:(thebasecas

4、es)5Thesubstitutionmethod(cont.)Guess:T(n)=O(nlgn).Prove:T(n)≤cnlgn(foraconstantc>0.)T(n)≤2(c⌊n/2⌋lg(⌊n/2⌋))+n≤cnlg(n/2)+n=cnlgn-cnlg2+n=cnlgn-cn+n≤cnlgn6Therecursion-treemethod(4.2)TherecursiontreeforT(n)=3T(n/4)+cn2——Drawingoutarecursiontreeisastraightforwardwaytodeviseagoodguess.C

5、ostofdividingproblem&combination…7TherecursiontreeforT(n)=3T(n/4)+cn23log4nBasecases8Themastermethod(4.3)f(n)«nlogbaT(n)=Θ(nlogba)f(n)=Θ(nlogba)T(n)=Θ(nlogbalgn)f(n)»nlogbaT(n)=Θ(f(n))T(n)=910ApplicationofMaster-theorem11ApplicationofMaster-theorem(cont.)12ApplicationofMaster-theorem

6、(cont.)13ApplicationofMaster-theorem(cont.)14ComputeFibonaccinumbers15ComputeFibonaccinumbers16关于上次课的作业冒泡法排序可以考虑通过一个increase变量替代重复的循环结构。最好能有“没有交换就停止”的策略。重排数组作业，设置头尾指针，交换正负，直到头=尾算法分析：注意区别最坏情况和平均情况的计算方法。参考教材p248的等概率情况下的算法代价分析。17Quicksort（chapter7）18Quicksort(cont.)Divide:Partition(rear

7、range)thearrayA[p‥r]intotwosubarraysA[p‥q-1]andA[q+1‥r]suchthat：eachelementofA[p‥q-1]<=A[q],inturn:A[q+1..r]>A[q]Conquer:SortthetwosubarraysA[p‥q-1]andA[q+1‥r]byrecursivecallstoquicksort.Combine:Sincethesubarraysaresortedinplace,noworkisneededtocombinethem:theentirearrayA[p‥r]isnowso

8、rted.19Quick