《算法导论》习题答案

1、Chapter2GettingStartInsertionsort2.1.2将Insertion-Sort重写为按非递减顺序排序2.1.3计算两个n位的二进制数组之和Analyzingalgorithms2.2.当k二1时，n二2，显然有T(n)=nlgn假设当k=i时公式成立，即T(n)=nlgn=2ilg2i=i-2i，则当k=i+1，即n=2i+1时，将函数n3/1000-100n2-100n+3用符号0表示2.2.2写出选择排序算法selection-sort当前n-1个元素排好序后，第n个元素已经是最大的元素了.最好时间和最坏时间均为0(n2)Designingalgorithms2

2、ifn二2T(n)斗2.3.3计算递归方程的解l2T(n/2)+nfn二2k，fork1T(n)=nlgn2.3.4给出insertionsort的递归版本的递归式T()=爲爲)f；=:2.3-6使用二分查找来替代insertion-sort中while循环内的线性扫描，是否可以将算法的时间提高到0(nlgn)?虽然用二分查找法可以将查找正确位置的时间复杂度降下来，但是移位操作的复杂度并没有减少，所以最坏情况下该算法的时间复杂度依然是0(n2)2.3-7给出一个算法，使得其能在0(nlgn)的时间内找出在一个n元素的整数数组内，是否存在两个元素之和为x首先利用快速排序将数组排序，时间0(nlg

3、n)，然后再进行查找:Search(A,n,x)QuickSort(A,n);i1；jn;whileAi+Aj丰xandijifAi+Aj0，(n+a)b=&(nb)a0时，(n+a)nb对于c=1,c=2b，cnb(n+a)cnb1212a0时，(n+a)-2a，当nn时，(n+a)(n/2)b00对于c=2-b,c=1，cnb(n+a)cnb121231-4判断2n+1与22n是否等于O)316证明如果算法的运行时间为0(g(n)，如果其最坏运行时间为O(g(n)，最佳运行时间为Q(g(n)。最坏时间O(g(n)，即Teg(n)1.T=0(g(n)3,1,7：证明o(g(n)nw(g(n)

4、=O定义3.2Standard3.2.2证明alogbc=Clogba=lgalgclgblgclog”a=logalgc=lgalgCblgblgaiogbc=logclgabalogbc=clogba3.2.3证明lg(n!)=0(nlgn)n!=(2n)andn!=o(n)lgn!=工lgi2nlgni=1i=1i=1i=1lg(n!)=0(nlgn)当n4时，i(n-i)22,:.n!=i(n-i)2nn!=w(2n)i=1n!e=em(lnm-1)mlnm-1nlnlnnlgn!不是多项式有界的。notationandcommonfunctions设|lglgn=m,m!mm(2m)

5、m=2m2m一1,n22m-1lglgn!22m-1n.lglgn是多项式有界的3.2.5比较lg(lg*n)与lg*(lgn)lg*(lgn)=lg*n-1设lg*n=x,lgxx-1lg*(lgn)较大。Chapter4RecurrencesTherecursion-tree4*1*1证明T(n)=T(n亏)+1的解为O(lgn)假设T(少2)clg(njb)clg(n/2-b+1)则T(n)clg(n2-b+1)+1=clg()+1=clg(n-2b+2)-clg2+1cLn/2lgLn/2+1T(n)2cLn/2lgLn/2+1+n=clgLn/2+1丄n+nc(n-1)lg(n/2)

6、+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)=Q(nlgn)T(n)=O(nlgn)4.1.3将假设改为T(n)=cnlgn+b,只需要在T(l)=l的情况下成立。4*1*6计算T(n)=2T(、不)+1的解令m=lgn,T(2m)=2T(2m/2)+1令T(n)=S(m),则S(m)=2S(m/2)+1其解为S(m)=0(m),T(n)=S(m)=0(lgn)Therecursion-treemethod4.2.1T(n)=0(nig3)4.2.24.2.3T(n)=0(n2)4.2.5T(n)=0(nlgn)Themastermethod4.3.1略4.3.4主方法是否适用方程T(n)一4T(n/2)+n2lgn,给出该方程解的一个上界不适用使用递归树方法可以求得其一个上界为O(n2lg2n)4.3.5给出某常数a1,b1和函数f(n)，使得其满足主定理case3中除了af(n/b)1,f(n)n,:,f(n)=0(n陀屮+g)=0(ng)，0g1