主定理学习笔记

主定理是分析分治算法复杂度的一个工具。 设分治的时间复杂度为 $T(n)$，其中 $n$ 为数据规模，且满足递推式： $T(n)=aT(\frac{n}{b})+O(n^d)$ 则有 $$T(n)=\{\begin{array}{llcc}O(n^d)& & & {\log }_{b}a<d\\ O(n^d{\log }_{b}n)& & & {\log }_{b}a=d\\ O(n^{{\log }_{b}a})& & & {\log }_{b}a>d\end{array}$$

---

推导： 不妨暴力展开柿子，得到： $T(n)=O(n^d+a(n/b{)}^d+a^2(n/b^2{)}^d+\cdots )=O(n^d)\sum _{k=0}^{{\log }_{b}n}{\left(\frac{a}{b^d}\right)}^k$ 当 $\frac{a}{b^d}<1$ 时,即$d>{\log }_{b}a$，$T(n)=O(n^d)$ 当 $d={\log }_{b}a$ 时， $T(n)=O(n^d{\log }_{b}n)$ 当 $d>{\log }_{b}a$ 时， $T(n)=O\left(n^d{\left(\frac{a}{b^d}\right)}^{{\log }_{b}n}\right)=O(n^d{a}^{{\log }_{b}n}{b}^{-d{\log }_{b}n})=O(n^{{\log }_{b}a})$