算法分析习题ppt课件.ppt

《算法分析习题ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机算法分析—习题课第四章：2、3、5、6、10第五章：2、3、8、9、11、121算法分析习题课4-22算法分析习题课4-2当g(n)=O(1)和f(n)=O(n)时不妨设g(n)=a，f(n)=bn，则：T(n)=2T(n/2)+bn=4T(n/4)+2bn=…=2kT(n/2k)+kbn=an+bnlog2n=O(nlog2n)3算法分析习题课4-2当g(n)=O(1)和f(n)=O(1)时，不妨设g(n)=c，f(n)=d，则：T(n)=2T(n/2)+d=4T(n/4)+2d=2kT(n/2k)+kd=…=cn+dlog2n=O(n)4算法分析习题课4

2、-3根据2.2节开始所给出的二分检索策略，写一个二分检索的递归过程。5算法分析习题课ProcedureBINSRCH(A,low,high,x,j)integermidiflow≤highthenmid←(low+high)/2case:x=A(mid):j←mid;return:x>A(mid):BINSRCH(A,mid+1,high,x,j):x

3、，然后检查2n/3处的元素。这样，或者找到x，或者把集合缩小到原来的1/3。分析算法在各种情况下的计算复杂度。7算法分析习题课ProcedureThriSearch(A,n,x,j)integerlow,high,p1,p2low←1;high←nwhilelow≤highdop1←(high+2low)/3p2←(2high+low)/3case:x=A(p1):j←p1;return:x=A(p2):j←p2;return:xA(p2):low←p2+1:else:low←p1+1;high←p2-1endcase

4、repeatj←0endThriSearch8算法分析习题课时间复杂度成功:O(1),O(log3(n)),O(log3(n))最好，平均，最坏失败:O(log3(n)),O(log3(n)),O(log3(n))最好，平均，最坏9算法分析习题课4-6对于含有n个内部结点的二元树，证明E=I+2n其中，E，I分别为外部和内部路径长度。证明：数学归纳法当n=1时，易知E=2，I=0，所以E=I+2n成立；假设n≤k(k>0)时，E=I+2n成立；10算法分析习题课则当n=k+1时，不妨认定某个内结点x，而且它为叶结点（一定存在这样的x，且设该结点的层数为h），将结点

5、x及其左右子结点（外结点）从原树中摘除（x替换为外结点）。X新树内部结点为k个,满足：Ek=Ik+2k(1)原树的内、外部路径长度：Ek+1=Ek-h+2(h+1)(2)Ik+1=Ik+h(3)综合(1)(2)(3)式：Ek+1=Ik+2k+h+2=Ik+1-h+2k+h+2=Ik+1+2(k+1)故命题成立。11算法分析习题课4-10过程MERGESORT的最坏情况时间是O(nlogn)，它的最好情况时间是什么？能说归并分类的时间是Θ(nlogn)吗？12算法分析习题课基于分治策略的算法-归并分类ProcedureMERGESORT(low,high)iflow

6、

7、题课第五章：2、3、8、9、11、1215算法分析习题课5-2①求以下情况背包问题的最优解，n=7，m=15，(p1,…,p7)=(10,5,15,7,6,18,3)和(w1,…,w7)=(2,3,5,7,1,4,1)。按照pi/wi的非增序可得(p5/w5,p1/w1,p6/w6,p3/w3,p7/w7,p2/w2,p4/w4)=(6,5,9/2,3,3,5/3,1)所以最优解为:(1,2/3,1,0,1,1,1)且FO(I)=166/316算法分析习题课5-2②将以上数据情况的背包问题记为I。设FG(I)是物品按pi的非增次序输入时由GREEDY-KNAPS

8、ACK所生