算法導(dǎo)論習(xí)題答案

1、Chapter2Getting Start2.1 Insertion sort2.1.2將Insertion-Sort重寫為按非遞減順序排序2.1.3計(jì)算兩個(gè)n位的二進(jìn)制數(shù)組之和2.2 Analyzing algorithms2.2.1 將函數(shù) n3/1000 -100n2 -100n+3 用符號。表示2.2.2寫出選擇排序算法 selection-sort當(dāng)前n-1個(gè)元素排好序后，第n個(gè)元素已經(jīng)是最大的元素了 最好時(shí)間和最壞時(shí)間均為O(n2)2.3 Designing algorithms2if n=2T(n)=,2.3.3計(jì)算遞歸方程的解ZWG+n if n = 2,forE1(1) 當(dāng)

2、k=1 時(shí)，n =2 ,顯然有 T(n) =nlg n(2) 假設(shè)當(dāng)k =i時(shí)公式成立，即T(n) = nlg n =2lg2=i 2 ,則當(dāng) k=i+1，即 n=2i4r時(shí),T(n) =T(2i 1) =2T(2) 2 1 = i 2 1 2 1 = (i 1) = 211 lg(2' 1 n Ig nT (n) = n Ig n2.3.4給出insertion sort的遞歸版本的遞歸式T(n)_0(1)一 T(n-1) 0(n)if n =1if n 12.3- 6使用二分查找來替代insertion-sort中1 while循環(huán)內(nèi)的線性掃描，是否可以將算法的時(shí)間提高到O(nlg

3、 n) ?雖然用二分查找法可以將查找正確位置的時(shí)間復(fù)雜度降下來，但 是移位操作的復(fù)雜度并沒有減少，所以最壞情況下該算法的時(shí)間復(fù)雜 度依然是Q(n2)2.3- 7給出一個(gè) 算法，使得其能在O(nlgn)的時(shí)間內(nèi)找出在一個(gè)n元素的整數(shù)數(shù)組內(nèi)，是否存在兩個(gè)元素之和為x首先利用快速排序?qū)?shù)組排序，時(shí)間O(nlgn),然后再進(jìn)行查找:Search(A,n,x) QuickSort(A,n); i 1; j n; while Ai+Aj = x and i<j if Ai+Aj<x i i+1 elsejJ1 if Ai+Aj=x return trueelsereturn false時(shí)間復(fù)雜

4、度為0(n)?；蛘咭部梢韵裙潭ㄒ粋€(gè)元素然后去二分查找 x減去元素的差，復(fù)雜度為Q(nlgn)Chapter3Growth of functions3.1Asymptotic notation3.1.2 證明對于 b>0,(n+a)b=O(nb)a0時(shí)，(n+a)b <(n + n)b =2bnb(n a)b nb對于 q =1,c2 =2b, qnb <(n +a)b <c2nba < 0時(shí)，(n +a)b < nb存在 n0 A2a，當(dāng) n >no 時(shí)，(n +a)b a (n/2)b對于 g =2義2 =1 , Gnb <(n +a)b &l

5、t;c2nb3.1-4判斷2時(shí)與22n是否等丁 O(2n)3.1.6證明如果算法的運(yùn)行時(shí)間為©(g(n)，如果其最壞運(yùn)行時(shí)間為O(g(n)，最佳運(yùn)行時(shí)間為 Q(g(n)。最壞時(shí)間 O(g(n)，即 T <c2g(n)；最佳時(shí)間 Q(g(n)，即 T Ac1g(n)T =”g(n)3.1.7:證明 o(g(n) "(g(n)=：，定義3.2 Standard notation and common functions3.2.2 證明 alogbC=clogbaiogb clg alg clg a b =logbclga =gblogb alg a lg clgc = l

6、ogb alg c =lgblogb clogb aa = c3 2 3 證明 lg(n!) =O(nlg n) n!=cc(2n) and n!=o(nn)nnlg n! = ' lgi ： ' lgn 二 nlgni 2i 4nn/2n/2n/22lgi =' lg i lg(n -i) =' lgi(n -i) ' lg( ) = nlgn -n nlg ni 4i =1i 4i=142lg(n!) - C-?(n lg n)n/2當(dāng) n>4時(shí)，i(n -i) >22,.n! =口 i (n-i) > 2n,.L n! =<

7、o(2n) i 4n! : nn, n! = o(nn)3.2.4 |lg n-!與l|lglg n 1是否多項(xiàng)式有界設(shè)lg n=m ,則 m! = 72(坦)me2m >(m)m = em(lnmT a mlnm a nlnlnn ee lgn!不是多項(xiàng)式有界的。m ，-m、m_ m2_2m 設(shè) lg lg n =m, m!：m : (2 )2: 22m1lg lg n -m -1, n Hcm 1. 一.g lg n = <2 壬nlg lg n"是多項(xiàng)式有界的3.2.5 比較 lg(lg*n)與 lg*(lg n)lg*(lgn)= lg*n-1設(shè) lg*n=x ,

8、 lgx<x-1 ig*(ign)較大。Chapter4Recurrences4.1 The recursion-tree 4.1.1 證明 T(n) =T(%1)+1 的解為 O(lgn)假設(shè) T( n、)壬clg( 修-b) £clg(n/2-b 1)n-2b+2則T(n) _clg( n、-b+1)+1=clg( -)+1=clg(n-2b+2)-clg2+1 -clg(n-b)T(n) =O(lg n)4.1.2 證明 T(n) =2T(E2j)+n 的解為 O(nlgn)設(shè)T(n 一)c"lgLn :T (n) _ 2c _n 以-llg k1 n = c

9、lg _n1 一 nn-c(n T)lg(n/2) n = cnlg nclg ncn n = cn(lg n 1) nc(lg n 2n)lg n +1 Mlg(n +1)，當(dāng) c <1/3,nc(lg n +2n)T(n) cnlg(n 1), T(n) ="(nlg n).T(n) =O(nlg n)4.1.3將假設(shè)改為T(n) = cn Ign +b，只需要在T(1)=1的情況下成立。4.1.6 計(jì)算 T(n)=2T(7F)+1 的解令 m =lgn,T(2m) =2T(2m/2) 1令 T(n)=S(m),則 S(m) =2S(m/2) +1其解為 S(m)-(m),

10、. T(n) = S(m)-(1g n)4.2 The recursion-tree method4.2.1 T (n) =0(n'g3)4.2.2 略4.2.3 T(n)=G>(n2)4.2.5T(n) =G»(nlg n)4.3 The master method4.3.1 略4.3.4主方法是否適用方程T(n) = 4T(n/2) + n2lgn ,給出該方程解的一個(gè)上界不適用使用遞歸樹方法可以求得其一個(gè)上界為O(n2 lg2n)4.3.5給出某常數(shù)aX,b1和函數(shù)f (n)，使得其滿足主定理 case3中除了 af (n/b) 4 cf (n)外的所有條件。f (n) =n(sin n+2) , a=1,b = 2, logba=0sin n 2 1, f (n) n,. f (n) = ”(nlogba )=“(n ), 0v ： 1af (n/b) =f (n/2) =n(sin(n/2) 2)/2若af(n/b)三cf