即：f(n)∈Θ(αg(n))

8．证明本节定理对于下列符号也成立： a.Ω符号 b.Θ符号 证明：

a。we need to proof that if t1(n)∈Ω(g1(n)) and t2(n)∈Ω(g2(n)), then t1(n)+ t2(n)∈Ω(max{g1(n), g2(n)})。 由 t1(n)∈Ω(g1(n))，

t1(n)≥c1g1(n) for all n>=n1, where c1>0 由 t2(n)∈Ω(g2(n))，

T2(n)≥c2g2(n) for all n>=n2, where c2>0 那么，取c>=min{c1,c2},当n>=max{n1,n2}时： 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使： a1*g1(n)<=t1(n)<=a2*g1(n)-----(1)

由t2(n)∈Θ(g2(n))知，存在非负整数b1,b2和n2使： 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).

显然，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)。 则（3）式转换为：

C1*max(g1,g2) <= t1(n)+t2(n) <=c2*2max(g1,g2)

所以当c1＝min(a1,b1),c2＝2c2=2max(c1,c2)，n0＝max(n1,n2)时，当n>=n0时上述不等式成立。 证毕。

习题2.4

1. 解下列递推关系 （做a,b） a.

?x(n)?x(n?1)?5当n>1时 ??x(1)?0 解：

5

b. ??x(n)?3x(n?1)当n>1时

?x(1)?4解：

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. 如果将这个算法和直截了当的非递归算法比，你做何评价？ 解：

6

a.

7. a. 请基于公式2n=2n-1+2n-1，设计一个递归算法。当n是任意非负整数的时候，该算法能够计算2n的值。

b. 建立该算法所做的加法运算次数的递推关系并求解

c. 为该算法构造一棵递归调用树，然后计算它所做的递归调用次数。 d. 对于该问题的求解来说，这是一个好的算法吗？ 解:

a.算法power(n)

nn-1n-1n

//基于公式2=2+2,计算2//输入:非负整数n //输出: 2n的值 If n=0 return 1

Else return power(n-1)+ power(n-1)

c.

7

C(n)??2i?2n?1?1 i?0n8.考虑下面的算法 算法 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.计算的给定数组的最小值 ?C(n?1)?1b.C(n)?? 0?for all n>1 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]) Temp2←Min2(A[l..(l+r)/2]+1..r) If temp1≤temp2 return temp1 Else return temp2 a.建立该算法所做的的操作次数的递推关系并求解 b.算法Min1和Min2哪个更快?有其他更好的算法吗? 解: a. 8