主定理

主定理适用于递归复杂度计算。

标准版：

$a,b$ 是常数，$f(n)$ 为额外附加值函数 $T(n)$ 为递归式 $T(n)=aT(\frac{n}{b})+f(n)\ (a>0,b>1)$，就有：

1. 当 $f(n)=\mathcal{O}(n^{(\log_ba)-\epsilon})$ 其中 $\epsilon>0$ 是一个常数（相当于 $\log_ba>f(n)$），则有 $T(n)=\Theta(n^{\log_ba})$；
2. 当 $f(n)=\Theta(n^{\log_ba})$，则有 $T(n)=\Theta(n^{\log_ba}\log n)$；
3. 当 $f(n)=\Omega(n^{(\log_ba)+\epsilon})$ 其中 $\epsilon>0$ 是一个常数（相当于 $\log_ba<f(n)$），且对于一个常数 $c<1$ 和所有足够大的 $n$ 有 $af(\frac{n}{b})\leq cf(n)$（这一条件在这里可以暂时忽略不看，但在证明时起到至关重要的作用），则有 $T(n)=\Theta(f(n))$.
4. 当 $f(n)=\Theta(n^{\log_ba}\log^kn)$ 其中 $k\geq1$ 是一个常数，则有 $T(n)=\Theta(n^{\log_ba}\log^{k+1}n)$；

举例：

例一：$T(n)=4T(\frac{n}{2})+n$，此时 $a=4,b=2,\epsilon=1$，那么 $\log_ba=\log_24=2,f(n)=\mathcal{O}(n^{\log_ba-\epsilon})=\mathcal{O}(n^{2-1})$，$f(n)$ 成立，所以 $T(n)=\Theta(n^{\log_ba})=\Theta(n^2)$。

例二：$T(n)=2T(\frac{n}{2})+n$，此时 $a=2,b=2$，那么 $\log_ba=\log_22=1,f(n)=\Theta(n^{\log_ba})=\Theta(n)$，$f(n)$ 成立，所以 $T(n)=\Theta(n^{\log_ba}\log n)=\Theta(n\log n)$。

例三：$T(n)=4T(\frac{n}{2})+n^3$，此时 $a=4,b=2,\epsilon=1$，那么 $\log_ba=\log_24=2,f(n)=\Omega(n^{\log_ba+\epsilon})=\Omega(n^{2+1})$，对于 $c=\frac{2}{3}$ 和够大的 $n$，$\left(af(\frac{n}{b})=4(\frac{n}{2})^3=4(\frac{n^3}{8})=\frac{n^3}{2}\right)\leq \left(cf(n)=\frac{2n^3}{3}\right)$，$f(n)$ 成立，所以 $T(n)=\Theta(f(n))=\Theta(n^3)$。

例四：$T(n)=2T(\frac{n}{2})+n\log n$，此时 $a=2,b=2,k=1$，那么 $\log_ba=\log_22=1,f(n)=\Theta(n^{\log_ba}\log^kn)=\Theta(n\log n)$，$f(n)$ 成立，所以 $T(n)=\Theta(n^{\log_ba}\log^{k+1}n)=\Theta(n\log^2 n)$。

简化版

将一个规模为 $n$ 的问题，通过分治得到 $a$ 个规模为 $\dfrac{n}{b}$ 的子问题，每次递归进行的计算为 $O(n^d)$，满足如下形式：

$$T(n)=a\cdot T(\dfrac{n}{b})+O(n^d)$$

则 $T(n)$ 满足：

$$T(n)=\begin{cases} O(n^d) & d> \log_b a\\ O(n^d\log n) & d= \log_b a\\ O(n^{\log_b a}) & d<\log_b a\\ \end{cases}$$

---

例如：

有递归式：

$$T(n)=\begin{cases} O(1) & n=1\\ 2T(\dfrac{n}{2})+n & \text{otherwise.} \end{cases}$$

则有 $a=2,b=2,d=1$。

$$\begin{array}{ll} \because 1=\log_22\\ \therefore T(n)=O(n^1\log n)=O(n\log n) \end{array}$$

---

另一例子：

$$T(n)=\begin{cases} O(1) & n=1\\ 2T(\dfrac{n}{2})+1 & \text{otherwise.} \end{cases}$$

则有 $a=2,b=2,d=0$。

$$\begin{array}{ll} \because 0<\log_22\\ \therefore T(n)=O(n^{\log_2 2})=O(n) \end{array}$$

---

例三：

$$T(n)=\begin{cases} O(1) & n=1\\ 2T(\dfrac{n}{2})+n\log n & \text{otherwise.} \end{cases}$$

则有 $a=2,b=2,d=1$。

$$\begin{array}{ll} \because 1=\log_22\\ \therefore T(n)=O(n^1\log n\cdot \log n)=O(n\log^2 n) \end{array}$$