# 主定理 > 原文： [https://www.programiz.com/dsa/master-theorem](https://www.programiz.com/dsa/master-theorem) #### 在本教程中，您将学习什么是主定理以及如何将其用于解决递归关系。 主定理是用于解决以下形式的递归关系的公式： ``` T(n) = aT(n/b) + f(n), where, n = size of input a = number of subproblems in the recursion n/b = size of each subproblem. All subproblems are assumed to have the same size. f(n) = cost of the work done outside the recursive call, which includes the cost of dividing the problem and cost of merging the solutions Here, a ≥ 1 and b > 1 are constants, and f(n) is an asymptotically positive function. ``` 渐近正函数表示对于`n`足够大的值，我们具有`f(n) > 0`。 主定理用于以简单快速的方式计算递归关系的时间复杂度（分治算法）。 * * * ## 主定理 如果`a ≥ 1`和`b > 1`是常数，并且`f(n)`是渐近正函数，则递归关系的时间复杂度由下式给出： ``` T(n) = aT(n/b) + f(n) where, T(n) has the following asymptotic bounds: 1\. If f(n) = O(nlog_b(a-ϵ)), then T(n) = Θ(nlog_b(a)). 2\. If f(n) = Θ(nlog_b(a)), then T(n) = Θ(nlog_b(a) *log n). 3\. If f(n) = Ω(nlog_b(a+ϵ)), then T(n) = Θ(f(n)). ϵ > 0 is a constant. ``` 以上每个条件都可以解释为： 1. 如果在每个级别上解决子问题的成本增加了某个因素，则`f(n)`的值将比`n logb a`减小几倍。 因此，时间复杂度受到最后一级的成本的压制。`n logb a` 2. 如果在每个级别上解决子问题的成本几乎相等，则`f(n)`的值将为`n logb a`。 因此，时间复杂度将为`f(n)`乘以级别总数，即。`n logb a * log n` 3. 如果解决每个级别上的子问题的成本降低了某个因素，则`f(n)`的值将比`n logb a`增大几倍。 因此，`f(n)`的成本抑制了时间复杂度。 * * * ## 主定理的求解示例 ``` T(n) = 3T(n/2) + n2 Here, a = 3 n/b = n/2 f(n) = n2 logb a = log2 3 ≈ 1.58 < 2 ie. f(n) < nlog_b(a+ϵ), where, ϵ is a constant. Case 3 implies here. Thus, T(n) = f(n) = Θ(n2) ``` * * * ## 主定理的局限性 在以下情况下，不能使用主定理： * `T(n)`不是单调的。 例如。`T(n) = sin n` * `f(n)`不是项。 例如。`f(n) = 2n` * `sum`不是常数。 例如。`a = 2n` * `a < 1`