主定理
主定理 \(\rm(Master\ Theorem)\) 被用来求解一类递归算法的时间复杂度，假设有递推式形如:
\[ T(n) = aT\left(\frac{n}{b}\right) + f(n) \]上式的含义是，存在一个规模为 \(n\) 的问题可以被划分成 \(a\) 个规模为 \(\frac{n}{b}\) 的问题，且将它们合并的运算复杂度为 \(f(n)\)。
那么根据主定理，有 ：
\[ T(n) = \begin{cases} \Theta\left(n^{\log _{b} a}\right) & f(n)=O\left(n^{\log _{b} a-\epsilon}\right) \\ \Theta(f(n)) & f(n)=\Omega\left(n^{\log _{b} a+\epsilon}\right) \\ \Theta\left(n^{\log _{b} a} \log ^{k+1} n\right) & f(n)=\Theta\left(n^{\log _{b} a} \log ^{k} n\right), k \geq 0 \end{cases} \]