在算法分析中，支配理论（英语：master theorem）提供了用渐近符号（大O符号）表示许多由分治法得到的递推关系式的方法。 -- Wikipedia

主定理的内容

若有一个问题的规模为 $n$ ，地推的子问题数量为 $a$ ，每个子问题的规模为 $ \frac{n}{b} $ ，递推之外的计算工作为 $f(n)$ ，则对于这个问题有如下的递推关系：

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

其中 $ a \geq 1, b > 1 $ ，$f(n)$ 是一个渐进非负函数。那么 $T(n)$ 可能有如下的渐进界：

1. 若 $ f(n) < n^{log\frac{a}{b}} $ ，且为多项式的小于，即 $ \exists \epsilon > 0 $ ，有 $ f(n) = O(n^{log\frac{a}{b} - \epsilon}) $ ，则 $ T(n) = \Theta(n^{log\frac{a}{b}}) $
2. 若 $ f(n) = n^{log\frac{a}{b}} $ ，则 $ T(n) = \Theta(n^{log\frac{a}{b}}logn) $
3. 若 $ f(n) > n^{log\frac{a}{b}} $ ，且为多项式的大于，即 $ \exists \epsilon > 0 $ ，有 $ f(n) = \Omega(n^{log\frac{a}{b} - \epsilon}) $ ，且对 $ \forall c < 1 $ 与所有足够大的 $n$ ，有 $ af(\frac{n}{b}) \leq cf(n) $ ，则 $ T(n) = \Theta(n^{log\frac{a}{b}}) $

证明

有时间就填坑，可以参考这里