《算法导论(第二版)》(中文版)课后答案.pdf

《《算法导论(第二版)》(中文版)课后答案.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《算法导论（第二版）》参考答案2.3-3数学归纳法证明即可，略（注：几乎所有人都对）2.3-4下面是最坏情况下的T(n)3.1-1证明：只需找出c1,c2,n0,使得0<=c1*(f(n)+g(n))<=max(f(n),g(n))<=c2*(f(n)+g(n))取c1=0.5,c2=1，由于f(n),g(n)是非负函数，所以在n>=0时恒成立，所以得证。3.1-8参照写定义即可，略（注：几乎所有人都对）注：题目中的要求使用递归树的方法，最好是像书上画一颗递归树然后进行运算。1《算法导论（第二版）》参考

2、答案注意题目中的要求使用递归树的方法，最好是像书上画一颗递归树然后进行运算。4.2.2证略4.2.3i由2n得i=lgnlgnlgn1i2122T(n)2cncn2cncn(n)i0214.3-12a)n2b)nlgn3c)n4.3-42《算法导论（第二版）》参考答案22nlgn7.1-2(1)使用P146的PARTION函数可以得到q=r注意每循环一次i加1，i的初始值为p1，循环总共运行(rp1)1次，最终返回的i1p1(r1)p11r(2)由题目要

3、求q=(p+r)/2可知，PARTITION函数中的i，j变量应该在循环中同时变化。Partition(A,p,r)x=A[p];i=p-1;j=r+1;while(TRUE)repeatj--;untilA[j]<=x;repeati++;untilA[i]>=x;if(i

4、是：N(n)=1+2*N(n/2)不难得到：N(n)=Θ（n）7.4-2T(n)=2*T(n/2)+Θ（n）可以得到T(n)=Θ（nlgn）由P46Theorem3.1可得：Ω(nlgn)13.1-5prove:3《算法导论（第二版）》参考答案13.1-6k2k2-12-113.2-313.3-513.4-34《算法导论（第二版）》参考答案14.1-414.2-214.2-3不可以，性能改变时间复杂度由O(lgn)->O(nlgn)14.3-2Note:注意Overlap的定义稍有不同，需要重新定义。算

5、法：只要将P314页第三行的改成>就行。14.3-3INTERVAL-SEARCH-SUBTREE(x,i)1whilex≠nil[T]andidoesnotoverlapint[x]2doifleft[x]≠nil[T]andmax[left[x]]≥low[i]3thenx←left[x]4elsex←right[x]5returnxINTERVAL-SEARCH-MIN(T,i)2y←INTERVAL-SEARCH-SUBTREE(root[T],i)先找第一个重叠区间3z←y4whiley≠n

6、il[T]andleft[y]≠nil[T]在它的左子树上查找5《算法导论（第二版）》参考答案5doz←y调用之前保存结果6y←INTERVAL-SEARCH-SUBTREE(y,i)如果循环是由于y没有左子树，那我们返回y否则我们返回z，这时意味着没有在z的左子树找到重叠区间7ify≠nil[T]andioverlapint[y]8thenreturny9elsereturnz15.1-5由FASTEST-WAY算法知：fj[]fj[1]ta122,jj11,fj[]fj[1]ta2

7、11,jj12,所以有：fj[]fj[]fj[1]tafj[1]ta1222,j11,j11,j12,j由课本P328（15.6）(15.7)式代入，可得：min([fj1]a,[fj1]ta)min([fj1]a,[fj1]ta)11,j22,j11,j22,j11,j12,jmin([fj1],[fj1]t)amin([fj1],[fj1]t)a122,j11,j211,j12,jfj[1]tafj[1]ta2

8、2,j11,j11,j12,j化简得：min([fj1],[fj1]t)min([fj1],[fj1]t)122,jj1211,1fj[1]tfj[1]t22,jj111,1而：min([fj1],[fj1]t)fj[1]t122,jj122,1min([fj1],[fj1]t)fj[1]t211,jj111,1等号在：fj[1]fj[1]t211,j1fj[