《算法设计与分析C++语言描述课后答案》由会员分享，可在线阅读，更多相关《算法设计与分析C++语言描述课后答案（23页珍藏版）》请在金锄头文库上搜索。
1、.第一章P151-3.最大公约数为1 。快 1414 倍。主要考虑循环次数， 程序 1-2 的 while 循环体做了10 次，程序 1-3 的 while 循环体做了14141 次（ 14142-2循环）若考虑其他语句，则没有这么多，可能就601 倍。第二章P322-8. （ 1）画线语句的执行次数为log n。(log n) 。划线语句的执行次数应该理解为一格整体。nijn(n1)(n2)(n3) 。（ 2）画线语句的执行次数为1。i 1j 1k 16（ 3）画线语句的执行次数为n。 (n ) 。（ 4）当 n 为奇数时画线语句的执行次数为(n1)(n3) ，4当 n 为偶数时画线语句的执
2、行次数为(n2)2。(n2 ) 。42-10. （ 1 ）当n1时 ， 5n28n25n2，所以，可选c5 ， n01 。 对 于 nn0 ，f ( n)5n28n25n2，所以， 5n28n2(n2 ) 。（ 2 ）当 n8时， 5n28n25n2n224n2 ，所以，可选c4 ， n08 。对于 nn0 ，f ( n)5n28n24n2 ，所以， 5n28n2(n2) 。（ 3）由（ 1 ）、（ 2 ）可知，取 c14 ， c25 ， n08 ，当 nn0 时，有 c1n25n28n 2c2 n2 ，所以 5n28n2(n2 ) 。2-11. (1) 当 n 3时， log nnlog 3
3、 n ，所以 f (n)20nlog n21n， g(n)n log 3 n2n 。可选 c21 ， n03 。对于 nn0 ， f ( n)cg(n) ，即 f (n)( g(n) 。注意：是 f(n )和 g (n )的关系。2;.（ 2） 当 n4时，log nnlog2 n ，所以f (n) n2 / log nn2 ，g (n)n log 2 nn2。可选 c1，n4。对于nn0 ， f ( n)n2cg(n) ，即f (n)( g(n) 。0（ 3）因为 f (n)(log n)log nnlog(log n) ，g(n)n / log nn logn2 。当 n4 时， f (
4、n)nlog(log n)n ，g(n)n log n 2n 。所以，可选c， n04 ，对于 nn0 ， f (n)cg(n) ，即f (n)(g (n) 。1第二章2-17.证明：设n2i，则 ilog n 。Tn2n2 logn 2 2Tn2nlogn2nlog nT2n222222Tn2n log nlog22nlog n2222Tn22nlog n2n2222Tn2nlogn2 2n log n2n232222223Tn2n log nlog422n log n2n2323Tn32n log n2n4n23L Lk Tn2knlognnnLn k122k2422i1 T 22 i1
5、nlog n2n4nL2n i22i142n log n log n1i2i1 n2n2n log 2 n2n log nlog 2 n3log n2 nn log 2 nn log n当n2 时， T n2nlog 2 n 。所以， Tnn log 2 n。;.第五章5-4. SolutionType DandC1(int left,int right)while(!Small(left,right)&leftright)int m=Divide(left,right);if(xPm)left=m+1;else return S(P);.5-7. template int SortableL
6、ist:BSearch(const T&x,int left,int right) constif (left=right)int m=(right+left)/3;if (xlm) return BSearch(x,m+1,right);else return m;return -1;第五章9 426135701234567-10证明：因为该算法在成功搜索的情况下，关键字之间的比较次数至少为logn ，至多为log n1。在;.不成功搜索的情况下，关键字之间的比较次数至少为log n1，至多为log n 2 。所以，算法的最好、最坏情况的时间复杂度为log n 。假定查找表中任何一个元素的概率是相等的，为1，那么，nAuElog n不成功搜索的平均时间复杂度为n，n1成功搜索的平均时间复杂度为As nI nE 2n nE1log n 。nnn其中， I 是二叉判定树的内路径长度，E 是外路径长度，并且EI2n。11.步数012345初始时11111111111
