第四章作業(yè)分析

1、精選優(yōu)質(zhì)文檔-傾情為你奉上本章作業(yè)：1.p98:11（實驗題）；5；2.p103:7；3.p105：2,3；4.p113:3第四章作業(yè)分析p98:習(xí)題4.14.1.5.求下列遞推式的解的增長次數(shù)。（鄭雪）a. T(n) = 4T( n/2 ) + n， T(1)=1b. T(n) = 4T( n/2 ) + ，T(1)=1c. T(n) = 4T( n/2 ) + ，T(1)=1解：解：由通用分治遞推式：T (n) = a T (n/b) + f(n)，a . a=4, b=2, f(n) = n = n d d=1 b d =2 < a=4T (n)。b . a=4, b=2, f(n

2、) = n2 = n d d=2 b d =2 = a=4T (n)。C . a=4, b=2, f(n) = n3 = n d d=3 b d =8 > a=4T (n)。p103: 習(xí)題4.24.2.7、對快速排序在平均情況下的遞推公式求解。（羅雨欣）解： Cavgn= 1n s=0n-1n+1+Cavgs+Cavgn-1-s =n+1+1n s=0n-1Cavgs+Cavgn-1-s =n+1+2n s=0n-1Cavgs 兩邊同乘以n得：nCavgn=n(n+1)+2s=0n-1Cavgs n=n-1時，有：(n-1) Cavgn-1=(n-1)n+2s=0n-2Cavgs 兩式

3、相減 - ：nCavgn=2n+(n+1)Cavgn-1 等式兩邊同除以n(n+1)有：Cavgnn+1=2n+1+Cavgn-1n 令Cavgnn+1=B(n)，則B(n)=B(n-1)+ 2n+1 (n2) 由Cavg0=Cavg1=1有B(0)=0， B(1)=1 此式可歸納為B(n)=2k=3n+11k，所以B(n)=2A(n+1)-3,其中A(n+1)= k=1n+11k， 下面證明1+12+13+14+1n= ln(n+1)+r(r為常量) Newton冪級數(shù)：ln(1+1x)= 1x-12×x2+13×x3-+(-1)n-11n×xn 于是，1x=

4、ln(1+1x)+ 12×x2-13×x3 帶入x=1,2,3n，就給出：11=ln(2)+ 12-13+14-15 12=ln(32)+ 12×4-13×8+14×16- 1n=ln(n+1n)+ 12×n2-13×n3+ 將上面帶入x后的所有等式相加有：1+12+13+14+.+1n= ln(n+1)+ 12(1+14+19+1n2)- 13(1+18+127+1n3)+ ，可以確定的是每一個括號中的級數(shù)都是收斂的，故我們可以定義k=1k+11k=1+12+13+14+1n= ln(n+1)+r(r為歐拉常數(shù)，約為0.5

5、77) ln(n+1) A(n+1)= k=1n+11k ln(n+1)，B(n)= 2A(n+1)-32 ln(n+1)， Cavgn=(n+1)B(n)=2(n+1) ln(n+1) 2nln n，得證！習(xí)題4.3 p105：（羅雨欣） 4.3.2. 當(dāng)n = 2k 時，用反向替換法求下面的遞推方程：log 2 n 當(dāng) n > 1 時， （n）= （ ）+ 1 ，（1） = 1 解法1：左邊： （n） =（2k）= + 1 = + 1 = k + 1 右邊：（ ）+ 1 =（ ）+ 1 =（2k-1）+ 1 = + 1 + 1 = + 2 = k + 1解法2當(dāng)n=2k時，用反向替換

6、法求下面的遞推方程： 當(dāng)n>1時，Cworstn=Cworstn/2+1，Cworst1=1（羅雨欣）解： 因為n=2k，n>1 將其帶入方程可得: Cworst2k=Cworst2k-1+1 且 Cworst1=1 做反向替換： Cworst2k=Cworst2k-1+1 =Cworst2k-2+2 =Cworst2k-3+3=Cworst2k-i+i=Cworst2k-k+k Cworst2k=1+k 又k=log2n Cworst2k=log2n+14.3. 3、a.證明下面的等式：（羅雨欣） 當(dāng)n1時，log2n+1=log2(n+1) b.請證明，對于大于0的任意奇數(shù)，方

7、程Cworstn=log2n+1是遞推關(guān)系(4.2)的解。解： a) 對于正整數(shù)n易有：2kn<2k+1，k0 k為正整數(shù) klog2n<log2n<k+1，k0 即有 log2n=k 同樣地，對于正整數(shù)n有2k<n+12k+1，k0 k為正整數(shù) k<log2(n+1)<log2(n+1)k+1，k0 即有 log2n+1=k+1 log2n+1=k+1=log2n+1，得證； b) 對于大于0的任意奇數(shù)n=2k+1，k>0 對于方程Cworstn=log2n+1有： Cworstn=Cworst2k+1=log22k+1+1=log22k+2=log

8、22+log2(k+1) =log2(k+1)+1 =log2k+1+1=log2k+2 對于遞推關(guān)系式(4.2) 當(dāng)n>1時，Cworstn=Cworstn/2+1，Cworst1=1 將n=2k+1，Cworstn=log2n+1代入化簡： Cworstn=Cworst2k+1=Cworst(2k+1)/2+1 =Cworstk+12+1 =Cworstk+1 =log2k+1+1=log2k+2 Cworst1=log21+1=1 由方程推知結(jié)果，再將方程與相應(yīng)的條件代入遞推關(guān)系式中得到相同的結(jié)果，當(dāng)然使此遞推關(guān)系式成立的解不僅為此方程，所以說方程Cworstn=log2n+1是遞推關(guān)系式Cworstn=Cworstn/2+1，Cworst1=1的解。P113 習(xí)題4.54.5.3、a.請證明等式alogbc=clogba，4.5節(jié)兩次使用了這個等式。 b.作為M(n)的閉合公式來說，為什么nlog23要比3log2n好？解： a) 對等式兩邊取自然對數(shù)有：左邊=ln(alogbc)= logbc·lna=lnclnb·lna 右邊=ln(clogba)= logba·lnc=