t1(n)+ t2(n)≥c1g1(n)+ c2g2(n)
≥c g1(n)+c g2(n)≥c[g1(n)+ g2(n)] ≥cmax{ g1(n), g2(n)}
所以以命题成立。
b. t1(n)+t2(n) ∈Θ(max(g1(n),g2(n)))
证明：由大?的定义知，必须确定常数c1、c2和n0，使得对于所有n>=n0，有：
c1max((g1(n),g2(n))?t1(n)?t2(n)?max(g1(n),g2(n))
由t1(n)∈Θ(g1(n))知，存在非负整数a1,a2和n1使： 由t2(n)∈Θ(g2(n))知，存在非负整数b1,b2和n2使：
a1*g1(n)<=t1(n)<=a2*g1(n)-----(1) b1*g2(n)<=t2(n)<=b2*g2(n)-----(2)
(1)+(2):
a1*g1(n)+ b1*g2(n)<=t1(n)+t2(n) <= a2*g1(n)+ b2*g2(n)
令c1=min(a1,b1),c2=max(a2,b2)，则
C1*(g1+g2)<= t1(n)+t2(n) <=c2(g1+g2)-----(3) 不失一般性假设max(g1(n),g2(n))=g1(n). 习题2.4
1. 解下列递推关系 （做a,b） a. 解：
显然，g1(n)+g2(n)<2g1(n)，即g1+g2<2max(g1,g2) 又g2(n)>0，g1(n)+g2(n)>g1(n),即g1+g2>max(g1,g2)。 C1*max(g1,g2) <= t1(n)+t2(n) <=c2*2max(g1,g2)
则（3）式转换为：
所以当c1＝min(a1,b1),c2＝2c2=2max(c1,c2)，n0＝max(n1,n2)时，当n>=n0时上述不等式成立。
证毕。
?x(n)?x(n?1)?5??x(1)?0当n>1时
b. 解：
?x(n)?3x(n?1)??x(1)?4当n>1时
5
2. 对于计算n!的递归算法F(n)，建立其递归调用次数的递推关系并求解。 解：
3. 考虑下列递归算法，该算法用来计算前n个立方的和：S(n)=13+23+…+n3。
算法S(n) //输入：正整数n //输出：前n个立方的和 if n=1 return 1
else return S(n-1)+n*n*n
a. 建立该算法的基本操作次数的递推关系并求解
b. 如果将这个算法和直截了当的非递归算法比，你做何评价？ 解： a.
7. a. 请基于公式2n=2n-1+2n-1，设计一个递归算法。当n是任意非负整数的时候，该算法能够计算2n的值。
b. 建立该算法所做的加法运算次数的递推关系并求解
c. 为该算法构造一棵递归调用树，然后计算它所做的递归调用次数。 d. 对于该问题的求解来说，这是一个好的算法吗？ 解:
a.算法power(n)
6
//基于公式2n=2n-1+2n-1,计算2n //输入:非负整数n //输出: 2n的值 If n=0 return 1 Else return power(n-1)+ power(n-1) c. nC(n)??2i?2n?1?1 i?08.考虑下面的算法 算法 Min1(A[0..n-1]) //输入:包含n个实数的数组A[0..n-1] If n=1 return A[0] Else temp←Min1(A[0..n-2]) If temp≤A[n-1] return temp Else return A[n-1] a.该算法计算的是什么? b.建立该算法所做的基本操作次数的递推关系并求解 解: a.计算的给定数组的最小值 b.C(n)??C(n?1)for all n>1 ??1?0 n=1 9.考虑用于解决第8题问题的另一个算法,该算法递归地将数组分成两半.我们将它称为Min2(A[0..n-1]) 算法 Min(A[r..l]) If l=r return A[l] Else temp1←Min2(A[l..(l+r)/2]) 7
Temp2←Min2(A[l..(l+r)/2]+1..r) If temp1≤temp2 return temp1 Else return temp2 a.建立该算法所做的的操作次数的递推关系并求解 b.算法Min1和Min2哪个更快?有其他更好的算法吗? 解: a. 习题2.6 1. 考虑下面的排序算法,其中插入了一个计数器来对关键比较次数进行计数. 算法SortAnalysis(A[0..n-1]) //input:包含n个可排序元素的一个数组A[0..n-1] //output:所做的关键比较的总次数 count←0 for i←1 to n-1 do v←A[i] j←i-1 while j>0 and A[j]>v do count←count+1 A[j+1]←A[j] j←j+1 A[j+1]←v return count 比较计数器是否插在了正确的位置?如果不对,请改正. 解:应改为: 算法SortAnalysis(A[0..n-1]) //input:包含n个可排序元素的一个数组A[0..n-1] //output:所做的关键比较的总次数 count←0 for i←1 to n-1 do v←A[i] j←i-1 while j>0 and A[j]>v do count←count+1 A[j+1]←A[j] j←j+1 if j>=0 count=count+1 A[j+1]←v 8
