原文： https://www.programiz.com/dsa/master-theorem

在本教程中，您将学习什么是主定理以及如何将其用于解决递归关系。

主定理是用于解决以下形式的递归关系的公式：

  1. T(n) = aT(n/b) + f(n),
  2. where,
  3. n = size of input
  4. a = number of subproblems in the recursion
  5. n/b = size of each subproblem. All subproblems are assumed 
  6.      to have the same size.
  7. f(n) = cost of the work done outside the recursive call, 
  8.       which includes the cost of dividing the problem and
  9.       cost of merging the solutions
  11. 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)是渐近正函数，则递归关系的时间复杂度由下式给出：

  1. T(n) = aT(n/b) + f(n)
  3. where, T(n) has the following asymptotic bounds:
  5.     1\. If f(n) = O(nlog_b(a-ϵ)), then T(n) = Θ(nlog_b(a)).
  7.     2\. If f(n) = Θ(nlog_b(a)), then T(n) = Θ(nlog_b(a) *log n).
  9.     3\. If f(n) = Ω(nlog_b(a+ϵ)), then T(n) = Θ(f(n)).
  11. ϵ > 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