主定理

主方法是一种用于解决如下形式的递推关系的公式：

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(nlogb a-ϵ), then T(n) = Θ(nlogb a).

    2. If f(n) = Θ(nlogb a), then T(n) = Θ(nlogb a * log n).

    3. If f(n) = Ω(nlogb a+ϵ), then T(n) = Θ(f(n)).

ϵ > 0 is a constant.    

上述每种情况都可以解释为：

1. 如果每层的子问题求解成本以某个因子增加，那么 f(n) 的值将比 nlogb a 在多项式意义上更小。因此，时间复杂度受最后一层成本的限制，即 nlogb a。
2. 如果每层子问题的求解成本几乎相等，那么 f(n) 的值将是 nlogb a。因此，时间复杂度将是 f(n) 乘以层数，即 nlogb a * log n。
3. 如果每层子问题的求解成本以某个因子减小，那么 f(n) 的值将比 nlogb 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) > nlogb 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
• a 不是常数。例如：a = 2n
• a < 1