主定理
在本教程中，您将学习什么是主定理以及如何将其用于解决递归关系。
主定理是用于解决以下形式的递归关系的公式：
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.
以上每个条件都可以解释为：
- 如果在每个级别上解决子问题的成本增加了某个因素，则
f(n)的值将比n logb a减小几倍。 因此，时间复杂度受到最后一级的成本的压制。n logb a - 如果在每个级别上解决子问题的成本几乎相等，则
f(n)的值将为n logb a。 因此，时间复杂度将为f(n)乘以级别总数，即。n logb a * log n - 如果解决每个级别上的子问题的成本降低了某个因素，则
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 nf(n)不是项。 例如。f(n) = 2nsum不是常数。 例如。a = 2na < 1