算法分析的那个定理.
Master Theorem
\[ T(n) = \begin{cases} \Theta(1), & \text{if } n = 1,\\ aT(n/b) + f(n), & \text{if } n>1. \end{cases} \]
where \(a\ge1\), \(b>1\) are constants and \(f\) is nonnegative. Then
- If \(f(n) = O(n^{\log_b a-\varepsilon})\) for some constant \(\varepsilon >0\), then \(T(n) = \Theta(n^{\log_b a})\).
- If \(f(n) = \Theta(n^{\log_b a})\), then \(T(n) = \Theta(n^{\log_b a}\lg n)\), where \(\lg n\) stands for \(\log_2 n\).
- If \(f(n) = \Omega(n^{\log_b a+\varepsilon})\) for some constant \(\varepsilon >0\), and if \(af(n/b)\le cf(n)\) for some constant \(c<1\) and all sufficiently large \(n\), then \(T(n) = \Theta(f(n))\).
直观上看就是比较 \(f(n)\) 与 \(n^{\log_b a}\) 的阶数, 其中大的决定了 \(T(n)\) 的阶数; 如果阶数相同则乘 \(\lg n\).
证明: 先对 \(n\) 为 \(b^k\), \(k\in\mathbb N\) 的情形证明, 下面的渐进符号都是对 \(n\) 在 \(b^k\) 上的点而言的. 写出递归树, 高度为 \(\log_b n\), 故有 \(a^{\log_b n} = n^{\log_b a}\) 个叶, 从而
\[
T(n) = \Theta(n^{\log_b a}) + g(n),
\] 其中
\[
g(n) = \sum_{j=0}^{\log_b n-1}a^j f(n/b^j).
\]
Case 1. \(f(n) = O(n^{\log_b a-\varepsilon})\), 易得 \(g(n) = O(n^{\log_b a})\).
Case 2. \(f(n) = \Theta(n^{\log_b a})\), 易得 \(g(n) = \Theta(n^{\log_b a} \log_b n) = \Theta(n^{\log_b a} \lg n)\).
Case 3. 首先 \(g(n) = \Omega(f(n))\). 又 \(af(n/b)\le cf(n)\) for some constant \(c<1\) and sufficiently large \(n\). 即 \(a^j f(n/b^j) \le c^j f(n)\). 得
\[
\begin{align*}
g(n) &= \sum_{j=0}^{\log_b n-1}a^j f(n/b^j)\&\le \sum_{j=0}^{\log_b n-1}c^j f(n) + O(1)\&\le f(n)\sum_{j=0}^\infty c^j + O(1)\&=O(f(n)).
\end{align*}
\]
故 \(g(n)=\Theta(f(n))\).
对一般的 \(n\) 证明略.
原文：https://www.cnblogs.com/shiina922/p/11125847.html