算法概论作业2.2

算法概论作业

---

2.3

(a)

由题解，假定对于某个常数c,有$O(n)≤cn$
且$T(n)=3T(n/2)+O(n)$
那么有

$$\begin{eqnarray*} T(n) & ≤ & 3T(n/2)+cn \\ & ≤ & 3[3T(n/4)+cn/2]+cn = 9T(n/4)+3cn/2+cn \\ & ≤ & 9[3T(n/8)+cn/4]+3cn/2+cn=27T(n/8)+9cn/4+3cn/2+cn \\ & \ldots & \end{eqnarray*}$$
从而，通项公式为：
$$T(n)≤3^kT(n/2^k)+\sum_{i=0}^{k-1} (3/2)^icn$$
很明显，$k=log_2n$

---

(b)

由题解，假定对于某个常数c,有$O(1)≤c$
且$T(n)=T(n-1)+O(1)$
那么有

$$\begin{eqnarray*} T(n) & ≤ & T(n-1)+c \\ & ≤ & T(n-2)+2c \\ & ≤ & T(n-3)+3c \\ & \ldots & \end{eqnarray*}$$
从而，通项公式为：
$$T(n)≤T(n-k)+kc$$
很明显，$k=n$
所以， $$T(n)=O(n)$$

---

2.4

首先，介绍求解递归式的几个方法：
1 主方法

2 替代法

猜测解的形式。
通过推导验证。
解出常数。

3 递归树方法
4 递推法

---

算法A:

$T(n)=5T(n/2)+O(n)$
很明显，递归式满足主定理模式，a=5，b=2，$f(n)=n$
$log_ba=log_25$,
又$∵ log_25>1$,
$∴T(n)=O(n^{log_25})$

---

算法B:

$T(n)=2T(n-1)+O(1)$
采用递推法，

$$\begin{eqnarray*} T(n) & ≤ & 2T(n-1)+c \\ & ≤ & 2^2T(n-2)+2c \\ & ≤ & 2^3T(n-3)+3c \\ & \ldots &\\ & ≤ & 2^nT(1)+nc \\ \end{eqnarray*}$$
所以，$T(n)=O(2^n)$

---

算法C:

$T(n)=9T(n/3)+O(n^3)$
很明显，递归式满足主定理模式，a=9，b=3，$f(n)=n^3$
$log_ba=log_39=2$,
又$∵ n^2<n^3$,
$T(n)=O(n^3)$

---

当n足够大时，很明显$T_a(n)<T_c(n)<T_b(n)$
所以算法A最优。

---

2.5

a)用递推法很快可以求出

$$T(n) = O(n^{log_32})$$

b)用主方法

$$T(n) = O(n^{log_45})$$
c)用主方法
$$T(n) = O(nlogn)$$
d)用主方法
$$T(n) = O(n^2logn)$$
e)用主方法
$$T(n) = O(n^3logn)$$
f)用替代法，由于前面是$log_{25},所以我们猜测大影响在后面$ $$T(n) = O(n^{3/2} log n)$$

g)用递推法

$$T(n) = O(n)$$
h) 用递推法 $$T(n) = O(n^c+1)$$
i) 用递推法 $$T(n) = O(c^n)$$
j)用递推法
$$T(n) = O(2^n)$$
k)