第四章作业分析(共5页).doc

本章作业：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、对快速排序在平均情况下的递推公式求解。（罗雨欣）解： Cavgn= 1n s=0n-1n+1+Ca