《《算法导论》习题答案.docx》由会员分享，可在线阅读，更多相关《《算法导论》习题答案.docx（8页珍藏版）》请在三一办公上搜索。
1、算法导论习题答案Chapter2 Getting Start 2.1 Insertion sort 2.1.2 将Insertion-Sort重写为按非递减顺序排序 2.1.3 计算两个n位的二进制数组之和 2.2 Analyzing algorithms 2.2.1将函数n3/1000-100n2-100n+3用符号Q表示 2.2.2写出选择排序算法selection-sort 当前n-1个元素排好序后，第n个元素已经是最大的元素了. 最好时间和最坏时间均为Q(n2) 2.3 Designing algorithms 2if n=2T(n)=k2T(n/2)+nif n=2,for k1 2
2、.3.3 计算递归方程的解 当k=1时，n=2，显然有T(n)=nlgn 假设当k=i时公式成立，即T(n)=nlgn=2ilg2i=i2i， 则当k=i+1，即n=2i+1时， T(n)=T(2i+1)=2T(2i)+2i+1=i2i+1+2i+1=(i+1)2i=2i+1lg(2i+1)=nlgn T(n)=nlgn 2.3.4 给出insertion sort的递归版本的递归式 Q(1)if n=1 T(n)=T(n-1)+Q(n)if n12.3-6 使用二分查找来替代insertion-sort中while循环内的线性扫描，是否可以将算法的时间提高到Q(nlgn)？ 虽然用二分查找法
3、可以将查找正确位置的时间复杂度降下来，但是移位操作的复杂度并没有减少，所以最坏情况下该算法的时间复杂度依然是Q(n2) 2.3-7 给出一个算法，使得其能在Q(nlgn)的时间内找出在一个n元素的整数数组内，是否存在两个元素之和为x 首先利用快速排序将数组排序，时间Q(nlgn)，然后再进行查找： Search(A,n,x) QuickSort(A,n); i1; jn; while Ai+Ajx and ij if Ai+Aj0,(n+a)b=Q(nb) a0时，(n+a)bnb 对于c1=1,c2=2b，c1nb(n+a)bc2nb a0时，(n+a)b-2a，当nn0时，(n+a)b(n
4、/2)b 对于c1=2-b,c2=1，c1nb(n+a)bc2nb 3.1-4 判断2n+1与22n是否等于O(2n) 3.1.6 证明如果算法的运行时间为Q(g(n)，如果其最坏运行时间为O(g(n)，最佳运行时间为W(g(n)。 最坏时间O(g(n)，即Tc1g(n) T=Q(g(n) 3.1.7：证明o(g(n)w(g(n)=F 定义 3.2 Standard notation and common functions 3.2.2 证明alogc=cloga bblgalogbc=logbclga=lgclogbalgalgclgblgalgc=logbalgc=lgb alogbc=c
5、logba 3.2.3nnlg(n!)=Q(nlgn)n!=w(2) and n!=o(n) 证明 lgn!=lgilg(i=1i=1i=1i=1nn/2n/2n/2n1)=nlgn-nnlgn422 lg(n!)=Q(nlgn) 当n4时，i(n-i)2，n!=i(n-i)2n,n!=w(2n) 2i=1n/2n!m=em(lnm-1)mlnm-1nlnlnn lgn！不是多项式有界的。 mememmmm2设lglgn=m，m!m(2)=222m-1lglgnm-1，n22lglgn!22m-1m-1n lglgn是多项式有界的3.2.5比较lg(lg*n)与lg*(lgn) lg*(lgn
6、)= lg*n-1 设lg*n=x，lgxx-1 lg*(lgn)较大。 Chapter4 Recurrences 4.1 The recursion-tree 4.1.1 证明T(n)=T(n2)+1的解为O(lgn) 假设T(n)clg(n-b)clg(n/2-b+1)22 n-2b+2则T(n)clg(n-b+1)+1=clg+1=clg(n-2b+2)-clg2+1clg(n-b)22T(n)=O(lgn) 4.1.2 证明T(n)=2T(n/2)+n的解为O(nlgn) 设T(n/2)cn/2lgn/2+1 T(n)2cn/2lgn/2+1+n=clgn/2+1 n+nc(n-1)l
7、g(n/2)+n=cnlgn-clgn-cn+n=cn(lgn+1)+n-c(lgn+2n)lgn+1lg(n+1)，当cc(lgn+2n) T(n)cnlg(n+1),T(n)=W(nlgn) T(n)=O(nlgn) 4.1.3 将假设改为T(n) = cn lgn +b，只需要在T(1)=1的情况下成立。 4.1.6 计算T(n)=2T(n)+1的解 令m=lgn,T(2m)=2T(2m/2)+1 令T(n)=S(m),则S(m)=2S(m/2)+1 其解为S(m)=Q(m),T(n)=S(m)=Q(lgn) 4.2 The recursion-tree method 4.2.1 T(n
8、)=Q(nlg3) 4.2.2 略 4.2.3 T(n)=Q(n2) 4.2.5 T(n)=Q(nlgn) 4.3 The master method 4.3.1 略 4.3.4 主方法是否适用方程T(n)=4T(n/2)+n2lgn，给出该方程解的一个上界 不适用 使用递归树方法可以求得其一个上界为O(n2lg2n) 4.3.5给出某常数a1,b1和函数f(n)，使得其满足主定理case3中除了af(n/b)cf(n)外的所有条件。 f(n)=n(sinn+2)，a=1,b=2， logba=0 Qsinn+21,f(n)n,f(n)=W(nlogba+x)=W(nx)，0x1 af(n/b)=f(n/2)=n(sin(n/2)+2)/2 若af(n/b)cf(n)则n(sin(n/2)+2)/2cn(sinn+2) sin(n/2)+2c2(sinn+2)找不到这样的c1，所以af(n/b)cf(n)不满足。 2(sinn+2)
