# 主定理 > 原文： [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`