Loading... > 在[算法分析](https://zh.wikipedia.org/wiki/算法分析)中，**支配理论**（英语：master theorem）提供了用渐近符号（[大O符号](https://zh.wikipedia.org/wiki/大O符号)）表示许多由[分治法](https://zh.wikipedia.org/wiki/分治法)得到的[递推关系式](https://zh.wikipedia.org/wiki/递推关系式)的方法。 -- 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}}) $ ## 证明 有时间就填坑，可以参考[这里](http://www.doc88.com/p-9761826142176.html) 最后修改：2020 年 04 月 15 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏