算法导论笔记 - 主方法求解递归式

1. 考虑递归式 T(n) = a * T(n/b) + f(n), 求其 T(n).

主方法对应的三种情况：

• $\forall \omega > 0, .s.t,$f(n) = $\color{red}{O(n^{log_b a - \omega})}$, 则 T(n) = $\color{red}{\theta(n^{log_b a})}$
• 若 f(n) = $\color{red}{\theta(n^{log_b a })}$, 则 T(n) = $\color{red}{\theta(n^{log_b a}lg n)}$
• $\forall \omega > 0$, .s.t, f(n) = $\color{red}{\Omega(n^{log_b a - \omega})}$， 且 如果 $\forall c < 1$和足够大的 n, .s.t, a * f(n/b) <= f(n), 则 T(n) = $\color{red}{\theta(f(n))}$

2. 如何理解？

关键在于比较 f(n) 与 $n^{log_b a}$

• 对于情况1， f(n) 不仅要小于 $n^{log_b a}$, 而且要多项式意义上的小于， 即对于足够大的 n， 有 $n^\omega > {n^{log_b a} \over f(n)}$
• 对于情况2，直观理解
• 对于情况3， f(n) 不仅要大于 $n^{log_b a}$，而且要多项式意义上的大于， 即对于足够大的 n, 有 $n^\omega > {f(n) \over n^{log_b a}}$, 且必须满足正则条件 $\forall c < 1$和足够大的 n, .s.t, a * f(n/b) <= f(n)

注：
1. 多项式意义上的大于，举个例子， $n^\omega$>$lgn$, 对任意的 $\omega > 0$和足够大的 n 成立
2. 主方法不能覆盖所有情况，当 $n^{log_b a}$大于但不多项式下大于，或者小于但不多项式下小于，则主方法不能用于求解递归式

3. 强化训练

a. $T(n) = 2T(n/2) + nlgn$

由表达式得知，$n^{log_b a} = n^{log_2 2}$, 由于 ${f(n) \over n^{log_b a}} = lgn$,
对于 任意的 $\omega$, 都不存在 $lgn > n^\omega$,
所以，T(n) 不可被主方法求解。

b. $T(n) = 3T(n/4) + n^2$

由表达式得知，$n^{log_b a} = n^{log_4 3}\approx n^{0.793}$,
所以 $\forall \omega \approx 0.2$，.s.t， $f(n)=\Omega(n^{log_b a + \omega})$

正则条件 $af(n/b) = 3{n^2 \over 4^2} = {3 \over 16}n^2$, 故 $\forall c = 3/16 < 1$, .s.t, $af(n/b)\le {3 \over 16}f(n)$
所以 $T(n) = \theta(n^2)$

c. $T(n) = 2T({n\over4})+\sqrt n$

由表达式得知，$n^{log_b a} = n^{log_4 2}=n^{1 \over 2}$,
由此知, $f(n) = \theta(n^{log_b a})$,
所以， $T(n) = \theta(n^{log_b a}lgn) = \theta(n^{1 \over 2}lgn)$

d. $T(n) = 4T({n\over4})+\sqrt n$

由表达式得知，$n^{log_b a} = n^{log_4 4}=n,

故 $\forall\omega={1 \over 2}$, .s.t, $f(n) = O(n^{log_b a - \omega})$
所以，$T(n)=\theta(n)$