第四章作业分析

本章作业：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)+2n，T(1)=1c.T(n)=4T(n/2)+3n，T(1)=1解：解：由通用分治递推式：T(n)=aT(n/b)+f(n)，a.a=4,b=2,f(n)=n=ndd=1bd=2a=4T(n)∈242baloglog（n）=（n）=（n）。b.a=4,b=2,f(n)=n2=ndd=2bd=2=a=4T(n)∈2d（nlogn）=（nlogn）。C.a=4,b=2,f(n)=n3=ndd=3bd=8a=4T(n)∈3d（n）=（n）。√p103:习题4.24.2.7、对快速排序在平均情况下的递推公式求解。（罗雨欣）解：==n+1+=n+1+两边同乘以n得：n=n(n+1)+2①n=n-1时，有：(n-1)=(n-1)n+2②两式相减①-②：n=2n+(n+1)③③等式两边同除以n(n+1)有：=+令=B(n)，则B(n)=B(n-1)+(n)由有B(0)=0，B(1)=1此式可归纳为B(n)=2，所以B(n)=2A(n+1)-3,其中A(n+1)=，下面证明1++++……+=ln(n+1)+r(r为常量)Newton幂级数：ln(1+)=-+-……+于是，=ln(1+)+-……带入x=1,2,3…n，就给出：=ln(2)+-+-……=ln()+-+-…………=ln()+-+……将上面带入x后的所有等式相加有：1++++...+=ln(n+1)+(1+++…+)-(1+++…+)+……，可以确定的是每一个括号中的级数都是收敛的，故我们可以定义=1++++……+=ln(n+1)+r(r为欧拉常数，约为0.577)ln(n+1)∴A(n+1)=ln(n+1)，B(n)=2A(n+1)-32ln(n+1)，=(n+1)B(n)=2(n+1)ln(n+1)2nlnn，得证！习题4.3p105：（罗雨欣）4.3.2.当n=2k时，用反向替换法求下面的递推方程：log2n当n1时，worstC（n）=worstC（2/n）+1，worstC（1）=1解法1：左边：worstC（n）=worstC（2k）=nlog2+1=k+1=k+1右边：worstC（2/n）+1=worstC（12k）+1=worstC（2k-1）+1=122logk+1+1=1k+2=k+1解法2当n=时，用反向替换法求下面的递推方程：当n1时，=+1，=1（罗雨欣）解：因为n=，n1将其带入方程可得:=+1且=1做反向替换：=+1=+2=+3=…=+i=…+k∴=1+k又∵k=∴=+14.3.3、a.证明下面的等式：（罗雨欣）当n1时，+1=b.请证明，对于大于0的任意奇数，方程=+1是递推关系(4.2)的解。解：a)对于正整数n易有：n，k0k为正整数∴k+1，k0即有=k同样地，对于正整数n有n，k0k为正整数∴k+1，k0即有k+1∴+1=k+1=，得证；b)对于大于0的任意奇数n=2k+1，k0对于方程=+1有：=+1===+1=+1+1=+2①对于递推关系式(4.2)当n1时，=+1，=1将n=2k+1，=+1代入化简：==+1=+1=+1=+1+1=+2②=+1=1由方程推知①结果，再将方程与相应的条件代入递推关系式中得到相同的结果①，当然使此递推关系式成立的解不仅为此方程，所以说方程=+1是递推关系式=+1，=1的解。P113习题4.54.5.3、a.请证明等式=，4.5节两次使用了这个等式。b.作为M(n)的闭合公式来说，为什么要比好？解：a)对等式两边取自然对数有：左边=ln()=·lna·lna右边=ln()=·lnc=·lnc=左边∴=得证；b)对于M(n)的闭合公式来说，显然比较和等指数为实数的表达式更为方便，而比较和则比较麻烦，故用要比处理M(n)的闭合公式更好。