主定理应试策略

序

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

策略

主定理形如：

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

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

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

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

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

3. 二者速度相当, 则最终 $T(n)\in \mathrm{\Theta }(n^{lo{g}_{b}a}lo{g}^{\epsilon +1}n)$, 注意有个 $+1$ 的存在.

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

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

例子

看几个例子。

维基百科

先是维基百科上的。

例 1 - 1

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

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

速度相当，取 $\epsilon =0$ 即可，s.t. $f(n)\in \mathrm{\Theta }(n^{lo{g}_{b}a}lo{g}^{\epsilon }n)$则 $T(n)=\mathrm{\Theta }(logn)$。

例 1 - 2

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

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

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

例 1 - 3

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

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

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

例 1 - 4

$$T(n)=2T(n/2)+\mathrm{\Theta }(n)$$

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

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

OI-WIKI

再看 OI-WIKI 的几个例子。

例 2 - 1

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

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

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

$$f(n)\in \mathrm{\Theta }(n^{0}lo{g}^{\epsilon }n)?$$

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

所以 $T(n)=\mathrm{\Theta }(f(n))=\mathrm{\Theta }(n)$

例 2 - 2

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

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

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

$$f(n)\in \mathrm{\Theta }(n^{0}lo{g}^{\epsilon }n)?$$

可以的，$\epsilon =1$ 即可，所以 $T(n)=\mathrm{\Theta }(lo{g}^{2}n)$

随堂小测

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

例 3 - 1

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

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

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

例 3 - 2

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

注意到 $lo{g}_{b}a=lo{g}_1.51=0$，所以基本操作是 $O(1)$ 的复杂度。而 $f(n)$ 是 $O(1)$。

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

例 3 - 3

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

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

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

$$f(n)\in \mathrm{\Theta }(n^{0.792}lo{g}^{\epsilon }n)?$$

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

例 3 - 4

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

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

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

$$f(n)\in \mathrm{\Theta }(n^{1}lo{g}^{\epsilon }n)?$$

可以的，$\epsilon =1$ 即可，所以 $T(n)=\mathrm{\Theta }(nlo{g}^{2}n)$

结语

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