序

主定理是用来分析递归算法复杂度的高效工具。不深究原理，只应试，下面给出应试策略。

策略

主定理形如：

$$
T(n) = aT(\frac{n}{b}) + f(n)
$$

主定理的核心是比较，到底递归到叶子结点的每个基本操作 ($log_b{a}$) 增长更快，还是减小问题规模 ($f(n)$) 的过程增长更快。

根据二者复杂度的强弱关系，分成三种情况：

  1. 基本操作增长(严格)更快, 则最终 $T(n) \in \Theta(n^{log_b{a}})$;

  2. 降低规模增长(严格)更快, 则最终 $T(n) \in \Theta(f(n))$, 但是需要满足一些条件, 否则进入情形 3;

  3. 二者速度相当, 则最终 $T(n) \in \Theta(n^{log_b{a}}log^{\varepsilon+1}{n})$, 注意有个 $+1$ 的存在.

其中第 2 点不能一步来判别，还需要验证一个式子 $af(\frac{n}{b}) \leq cf(n)$（即递归调用的贡献足够小）

不过没关系，既然分成了三个 case，不妨用排除法，把剩下两种可能都排除掉，就只剩下第 2 种了。

例子

看几个例子。

维基百科

先是维基百科上的。

例 1 - 1

$$
T(n) = T(n/2) + \Theta(1)
$$

注意到 $log_b{a} = log_2{1} = 0$，所以基本操作是 $O(1)$ 的复杂度。而 $f(n)$ 也是 $O(1)$(不要被 $\Theta$ 吓到，$O$ 是更弱的 $\Theta$，只有上界)。

速度相当，取 $\varepsilon = 0$ 即可，s.t. $f(n) \in \Theta(n^{log_b{a}}log^{\varepsilon}n)$则 $T(n) = \Theta(logn)$。

例 1 - 2

$$
T(n) = 2T(n/2) + \Theta(1)
$$

注意到 $log_b{a} = log_2{2} = 1$，所以基本操作是 $O(n)$ 的复杂度。而 $f(n)$ 是 $O(1)$。

基本操作更快，是情形 1，直接 $T(n) = \Theta(n)$。

例 1 - 3

$$
T(n) = 2T(n/2) + O(logn)
$$

注意到 $log_b{a} = log_2{2} = 1$，所以基本操作是 $O(n)$ 的复杂度。而 $f(n)$ 是 $O(logn)$。

基本操作快，是情形 1，直接 $T(n) = \Theta(n)$。

例 1 - 4

$$
T(n) = 2T(n/2) + \Theta(n)
$$

注意到 $log_b{a} = log_2{2} = 1$，所以基本操作是 $O(n)$ 的复杂度。而 $f(n)$ 是 $O(n)$。

速度相当，$f(n) \in \Theta(n^{1}log^{0}n)$，则 $T(n) = \Theta(nlogn)$。

OI-WIKI

再看 OI-WIKI 的几个例子。

例 2 - 1

$$
T(n) = T(n/2) + n
$$

注意到 $log_b{a} = log_2{1} = 0$，所以基本操作是 $O(1)$ 的复杂度。而 $f(n)$ 是 $O(n)$。

f(n) 更慢，要先排除情形 1。然后，情形三能满足吗？

$$
f(n) \in \Theta(n^{0}log^{\varepsilon}n)?
$$

没有这样的 $\varepsilon$，所以情形 3 不满足，只有可能是 2。

所以 $T(n) = \Theta(f(n)) = \Theta(n)$

例 2 - 2

$$
T(n) = T(n/2) + logn
$$

注意到 $log_b{a} = log_2{1} = 0$，所以基本操作是 $O(1)$ 的复杂度。而 $f(n)$ 是 $O(logn)$。

f(n) 更慢，要先排除情形 1。然后，情形三能满足吗？

$$
f(n) \in \Theta(n^{0}log^{\varepsilon}n)?
$$

可以的，$\varepsilon = 1$ 即可，所以 $T(n) = \Theta(log^{2}n)$

随堂小测

再看课堂上的随堂测试题。

例 3 - 1

$$
T(n) = 9T(n/3) + n
$$

注意到 $log_b{a} = log_3{9} = 2$，所以基本操作是 $O(n^2)$ 的复杂度。而 $f(n)$ 是 $O(n)$。

基本操作慢，所以直接 $T(n) = \Theta(n^2)$

例 3 - 2

$$
T(n) = T(2n/3) + 1
$$

注意到 $log_b{a} = log_1.5{1} = 0$，所以基本操作是 $O(1)$ 的复杂度。而 $f(n)$ 是 $O(1)$。

速度相当，所以直接情形 3：$T(n) = \Theta(logn)$

例 3 - 3

$$
T(n) = 3T(n/4) + nlogn
$$

注意到 $log_b{a} = log_4{3} \approx 0.792$，所以基本操作是 $O(n^{0.792})$ 的复杂度。而 $f(n)$ 是 $O(nlogn)$。

f(n) 更慢，要先排除情形 1。然后，情形 3 能满足吗？

$$
f(n) \in \Theta(n^{0.792}log^{\varepsilon}n)?
$$

不太行，所以情形 2，$T(n) = \Theta(nlogn)$

例 3 - 4

$$
T(n) = 2T(n/2) + nlogn
$$

注意到 $log_b{a} = log_2{2} = 1$，所以基本操作是 $O(n)$ 的复杂度。而 $f(n)$ 是 $O(nlogn)$。

而 $O(nlogn)$ 比 $O(n)$ 慢，也就是 $f(n)$ 更慢，看看情形 3 满足吗？

$$
f(n) \in \Theta(n^{1}log^{\varepsilon}n)?
$$

可以的，$\varepsilon = 1$ 即可，所以 $T(n) = \Theta(nlog^{2}n)$

结语

总结了一些应试技巧，应该能覆盖所有的题目了，目前还没找到 bug。