主定理与主方法的使用

主定理

令 $a \geqslant 1$ 和 $b > 1$ 是常数, $f(n)$ 是一个函数, $T(n)$ 是定义在非负整数上的递归式:

\[T(n) = aT(n/b) + f(n)\]

其中我们将 $n/b$ 解释为 $\left \lfloor n/b \right \rfloor$ 或 $\left \lceil n/b \right \rceil$. 那么 $T(n)$ 有如下渐进界:

1. 若对某个常数 $\varepsilon > 0$ 有 $f(n) = O(n^{log_{b}a - \varepsilon})$, 则 $T(n) = \Theta(n^{log_{b}a})$.
2. 若 $f(n) = \Theta(n^{log_{b}a})$, 则 $T(n) = O(n^{log_{b}a}lgn)$.
3. 若对某个常数 $\varepsilon > 0$ 有 $f(n) = \Omega(n^{log_{b}a + \varepsilon})$, 且对某个常数 $c < 1$ 和所有足够大的 $n$ 有 $af(n/b) \leqslant cf(n)$, 则 $T(n) = \Theta(f(n))$.

使用主方法

使用主方法很简单, 我们只需确定主定理的哪种情况成立, 即可得到解.

我们看下面的例子

\[T(n) = 9T(n/3) + n\]

对于这个递归式, 我们有 $a = 9$, $b = 3$, $f(n) = n$, 因此 $n^{log_{b}a} = n^{log_{3}9} = \Theta(n^2)$. 由于 $f(n) = O(n^{log_{3}9 - \varepsilon})$, 其中 $\varepsilon = 1$, 因此可以应用主定理的情况 1, 从而得到解 $T(n) = \Theta(n^2)$.

参考

《算法导论》（中文版）