《算法分析与设计》——第 1-2 章习题参考解答 1.13 解答： f(n) 2n3+3n 50n+log n 50nlog n g(n) 100n2+2n+100 10n+log log n 10nlog log n log n n! log2 n 5n f=O(g) False True False True False f=(g) True True True False True f=(g) False True False False False 1.14 解答： (a) 因 (b) 因 (c) 因 (d) 因  n  n  n 2 lim 3 n 7 lim 5.1 n 3 lim n 2 lim  n   5.1 n  n 100 log3 n n 1000 3 n 5.1 n n log n log nn !  100 n ! ，所以，2n+3log100n=(n)。 2  n log  n 3  7 ，所以，7n3+1000nlog n+3n =(n3). ，所以，3n1.5+n1.5log n=(n1.5log n).  1 ，所以，2n+100n+ n!=(n!). 1   n 1.16 解答： (a) 算法执行元素比较运算的最小次数是 n－1。当输入 A[1..n] 已经有非减次序时该算法执 行元素比较运算次数达到这个最小值。 (b) 算法执行元素比较运算的最大次数是(n－1)+( n－2)+…+ 2+1=n(n－1)/2。当输入 A[1..n] 已有递减次序时该算法执行元素比较运算次数达到这个最大值。 (c) 算法执行元素赋值运算的最小次数是 0。当输入 A[1..n] 已经有非减次序时该算法执行元 素赋值运算次数达到这个最小值。 (d) 算法执行元素赋值运算的最大次数是 3[(n－1)+( n－2)+…+ 2+1]=3n(n－1)/2。当输入 A[1..n] 已有递减次序时该算法执行元素赋值运算次数达到这个最大值。 (e) 使用记号 O 和 ，算法 BUBBLESORT 的运行时间分别表示为(n2)和(n)。 (f) 该算法的运行时间不能使用记号来表示，这是因为算法的运行时间范围为 n 的一次方 到二次方。 2.16 解答： (a) 一方面，∑j=1 另一方面，∑j=1 ≥n/2 n/2log n/2 ≥(n-1)n/4·log(n/2)。 n nlog n≤n 2 log n， n jlog j≥∑j= n/2 n n/2log n/2 n jlog j≤∑j=1 因此，∑j=1 n jlog j= (n 2logn)。 （b）令 f(x)=x log x (x≥1)。由于 f(x) 是增函数，故有 n jlog j≤∫1 n+1 x log xdx≤(2(n+1)2 ln(n+1)-(n+1)2+1) / (4ln2)； n jlog j=∑j=2 n jlog j≥∫1 n x log xdx≥(2n2 lnn-n2+1) / (4ln2)。 n jlog j= (n 2lnn)=  (n 2logn)。 ∑j=1 同时， ∑j=1 因此，∑j=1 2.18 解答： (a) 特征方程为 x=3。 陈卫东(chenwd@scnu.edu.cn) 1 华南师范大学 计算机学院 

《算法分析与设计》——第 1-2 章习题参考解答 因此， f(n)=c·3n （n≥0），其中 c 由初始条件 f(0)确定。 解方程 f(0)=5=c，得 c=5。 于是，f(n)=5·3n （n≥0）。 (b) 特征方程为 x=2。 因此，f(n)=c·2n （n≥0），其中 c 由初始条件 f(0)确定。 解方程 f(0)=2=c，得 c=2。 于是，f(n)=2n+1 （n≥0）。 2.19 解答： (a) 特征方程为 x2-5x +6=0， 其解为 x1=2，x2=3。 因此，递归方程的解为 f(n)= c1·2n + c2·3n （n≥0）。常数 c1 和 c2 由下列方程组确定： f(0)=1= c1 + c2， f(1)=0=2c1 + 3c2。 解此方程组得 c1=3，c2 = -2。 于是，f(n)=3·2n-2·3n （n≥0）。 (b) 特征方程为 x2-4x +4=0，其解为 x1=x2=2。 因此，递归方程的解为 f(n)= c1·2n + c2·n 2n （n≥0）。 常数 c1 和 c2 由下列方程组确定： f(0)=6= c1， f(1)=8=2c1 +2c2。 解此方程组得 c1=6，c2 = -2。 于是，f(n)=3·2n+1-n·2n+1 （n≥0）。 2.20 解答： (a) f(n)= f(n-1)+ n2 = f(n-2)+(n-1)2+n2=…… = f(0)+12+22+…+(n-1)2+n2 =0+12+22+…+(n-1)2+n2 =n(n+1)(2n+1)/6 （n≥0）。 (b) 令 f(n)= 2ng(n)（g(0)=f(0)=1）。于是， 2ng(n)= 2·2n-1g(n-1)+n， 从而有方程 g(n)=g(n-1)+n·2-n。 其解为 g(n) =∑i=1 n i·2-i +1 = 2-(n+2)/2n+1 =3-(n+2)/2n （n≥0）。 因此， f(n)= 3·2n-n-2 （n≥0）。 (c) 令 f(n)=3ng(n)（g(0)=f(0)=3）。于是， 3ng(n)=3·3n-1g(n-1)+ 2n， 从而有方程 g(n)=g(n-1)+(2/3)n。 其解为 g(n) = g(0)+∑i=1 n(2/3) i n(2/3) i =3+∑i=1 =5-2(2/3) n （n≥0）。 因此， f(n)= 5·3n-2n+1 （n≥0）。 陈卫东(chenwd@scnu.edu.cn) 2 华南师范大学 计算机学院