第四章作业分析

1、本章作业：1.p98:11（实验题）；5；2.p103:7；3.p105：2,3；4.p113:3第四章作业分析p98:习题4.14.1.5.求下列递推式的解的增长次数。（郑雪）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)。p103: 习题4.24.2.7、对快速排序在平均情况下的递推公式求解

2、。（罗雨欣）解： 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 两式相减 - ：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)

3、=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幂级数：ln(1+1x)= 1x-12x2+13x3-+(-1)n-11nxn 于是，1x= ln(1+1x)+ 12x2-13x3 带入x=1,2,3n，就给出：11=ln(2)+ 12-13+14-15 12=ln(32)+ 124-138+1416- 1n=ln(n+1n)+ 12n2-13n3+ 将上面带入x后的所有等式相加有：1+12+13+14+.+1n= ln(n

4、+1)+ 12(1+14+19+1n2)- 13(1+18+127+1n3)+ ，可以确定的是每一个括号中的级数都是收敛的，故我们可以定义k=1k+11k=1+12+13+14+1n= ln(n+1)+r(r为欧拉常数，约为0.577) 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，得证！习题4.3 p105：（罗雨欣） 4.3.2. 当n = 2k 时，用反向替换法求下面的递推方程：log 2 n 当 n 1 时， （n）= （ ）+ 1 ，（1

5、） = 1 解法1：左边： （n） =（2k）= + 1 = + 1 = k + 1 右边：（ ）+ 1 =（ ）+ 1 =（2k-1）+ 1 = + 1 + 1 = + 2 = k + 1解法2当n=2k时，用反向替换法求下面的递推方程： 当n1时，Cworstn=Cworstn/2+1，Cworst1=1（罗雨欣）解： 因为n=2k，n1 将其带入方程可得: Cworst2k=Cworst2k-1+1 且 Cworst1=1 做反向替换： Cworst2k=Cworst2k-1+1 =Cworst2k-2+2 =Cworst2k-3+3=Cworst2k-i+i=Cworst2k-k+k

6、Cworst2k=1+k 又k=log2n Cworst2k=log2n+14.3. 3、a.证明下面的等式：（罗雨欣） 当n1时，log2n+1=log2(n+1) b.请证明，对于大于0的任意奇数，方程Cworstn=log2n+1是递推关系(4.2)的解。解： a) 对于正整数n易有：2kn2k+1，k0 k为正整数 klog2nlog2nk+1，k0 即有 log2n=k 同样地，对于正整数n有2kn+12k+1，k0 k为正整数 klog2(n+1)0 对于方程Cworstn=log2n+1有： Cworstn=Cworst2k+1=log22k+1+1=log22k+2=log22

7、+log2(k+1) =log2(k+1)+1 =log2k+1+1=log2k+2 对于递推关系式(4.2) 当n1时，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 由方程推知结果，再将方程与相应的条件代入递推关系式中得到相同的结果，当然使此递推关系式成立的解不仅为此方程，所以说方程Cworstn=log2n+1是递推关系式Cworstn=Cworstn/2+1，Cworst1=1的解。P113 习题4.54.5.3、a.请证明等式alogbc=clogba，4.5节两次使用了这个等式。 b.作为M(n)的闭合公式来说，为什么nlog23要比3log2n好？解： a) 对等式两边取自然对数有：左边=ln(alogbc)= logbclna=lnclnblna 右边=ln(clogba)= logbalnc=lna