算法设计与分析C语言描述陈慧南版课后答案

《算法设计与分析C语言描述陈慧南版课后答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、百度文库・让每个人平等地提升自我第一章1-3.最大公约数为1。快1414倍。主要考虑循环次数，程序1-2的while循环体做了10次，程序1-3的while循环体做了14141次(14142-2循环)若考虑其他语句，则没有这么多，可能就601倍。第二章%2-8.(1)画线语句的执行次数为「log”］。O(logn)0划线语句的执行次数应该理解为一格整体。(2)画线语句的执行次数为/-1"16(3)画线语句的执行次数为［而_。0(、万)。(4)当n为奇数时画线语句的执行次数为S+DS+3),4当n为偶数时画线语句的执行次数为史立，0(r)042-10.(1)当〃之1时，5/z2-

2、8/2+2<5/?2,所以，可选c=5,n()=1o对于〃之〃口,f(n)=5/?2-8/7+2<5n2,所以，5/i2-8〃+2=0(/)°(2)当n>8时，5n2-8n+2>5n2-n2+2>4n2,所以，可选c=4,n0=8a对于一2％,/(〃)=5〃2-8〃+2之4〃2,所以，5/r-8/7+2=Q(7?2)o(3)由(1)、(2)可知，取q=4,q=5，〃o=8，当〃之时，有卬/K5//一8〃+2«cy/,所以5/—8〃+2=。(〃2)b2-11.(1)当〃之3时，Iog/?2〃。可

3、21选c=—，〃o=3©对于〃之〃0，f(n)即/(〃)=O(g(〃))。注意：是大〃)和g(〃)的关系。2(2)当〃24时，log〃<〃/?(),f(n)4时，/(〃)=/0g械")，10百度文库・让每个人平等地提升自我g(〃)=〃log〃2<〃。所以，可选c=l,"o=4,对于"2%,/(〃)2cg(〃)，即/(〃)=C(g(〃))。第二章T(n)=2T+

4、2/?log77=22T+277log7Z2-17.证明：设〃=2'，则z=logno10百度文库・让每个人平等地提升自我10百度文库・让每个人平等地提升自我=23T=23T+3x2nlogn-2〃一4〃+2x2〃log77-2/7+2x—xlog—+2x2/1logn-2n+2n(logn-log4)+2x2nlogn-2n=2kT_^-jj+2knlogn-2n-4/?2n(k-1)=222)+2(i-l)〃log〃-2〃-4〃2n(i-2)=2/_x4+2,Hog//(log/2-1)-(/-2)(/-1)/?=2〃+Inlog2//-2〃logzz-(log2n-3l

5、ogn+2)n=nlog2n+nlogn当n>2时，r(7?)<2/?lOg2/?o所以，r(H)=O(7?log272)o10百度文库・让每个人平等地提升自我第五章5-4.SolutionTypeDaiidCl(intleftjntright)while(!Small(left,right)&&leftP[m])left=m+1;elserenirnS(P)5-7.templatemtSortableList::BSearch(constT

6、&x,intleft,intright)const(if(left<=nght)(mtm=(nght+left)/3;if(xl[m])returnBSearch(x,m+l,riglit);elsereturnm;)return-1;}第五章10百度文库・让每个人平等地提升自我10百度文库・让每个人平等地提升自我证明：因为该算法在成功搜索的情况下，关键字之间的比较次数至少为至多为在10百度文库・让每个人平等地提升自我不成功搜索的情况下，关键字之间的比较次数至少为］log〃」+l，至多为［k)g〃」+2。所以，算

7、法的最好、最坏情况的时间复杂度为。(log”)。假定查找表中任何一个元素的概率是相等的，为!，那么，n一F.、不成功搜索的平均时间复杂度为4,(〃)=--=O(log/2)，74-17F—977-4-/?F成功搜索的平均时间复杂度为A(〃)=—==--1=O(logn)onnn其中，/是二叉判定树的内路径长度，E是外路径长度，并且七=1+2〃。11.步数012345初始时111111[11]1[11]82[1]11[11]83111[11]CO4111[1]1CO排序结果11111CO步数0