跳到主要内容

主定理

提示
  1. 主定理定义：主定理是一个用于快速计算分治算法递归关系式时间复杂度的公式，适用于形式为 T(n) = aT(n/b) + f(n) 的递归关系。
  2. 递归关系条件：在主定理中，a 代表递归中子问题的数量，n/b 是每个子问题的大小，f(n) 是递归调用外的工作成本，且 a ≥ 1，b > 1。
  3. 时间复杂度计算：根据 f(n) 和 nlogb a 的关系，时间复杂度可分为三种情况：O(nlogb a)，Θ(nlogb a * log n) 或 Θ(f(n))。

主定理是一个公式，用于解决形式如下的递归关系：

T(n) = aT(n/b) + f(n),
其中，
n = 输入的大小
a = 递归中子问题的数量
n/b = 每个子问题的大小。假设所有子问题的大小相同。
f(n) = 递归调用外完成的工作的成本，
      包括分割问题的成本和合并解决方案的成本

这里，a ≥ 1 且 b > 1 是常数，f(n) 是一个渐近正函数。

渐近正函数意味着对于足够大的 n，我们有 f(n) > 0。

主定理用于以简单和快速的方式计算递归关系（分治算法）的时间复杂度。

主定理​

如果 a ≥ 1 和 b > 1 是常数且 f(n) 是渐近正函数，则递归关系的时间复杂度由下式给出：

T(n) = aT(n/b) + f(n)

其中，T(n) 有以下渐近界限：

    1. 如果 f(n) = O(nlogb a-ϵ)，则 T(n) = Θ(nlogb a)。

    2. 如果 f(n) = Θ(nlogb a)，则 T(n) = Θ(nlogb a * log n)。

    3. 如果 f(n) = Ω(nlogb a+ϵ)，则 T(n) = Θ(f(n))。

ϵ > 0 是一个常数。

以上每个条件可以解释为：

  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) + n^2
这里，
a = 3
n/b = n/2
f(n) = n^2

logb a = log2 3 ≈ 1.58 < 2

即 f(n) < nlogb a+ϵ ，其中，ϵ 是一个常数。

这里适用情况 3。

因此，T(n) = f(n) = Θ(n^2)

主定理的局限性​

如果以下情况发生，主定理不适用：

  • T(n) 不是单调的。例如：T(n) = sin n
  • f(n) 不是多项式。例如：f(n) = 2^n
  • a 不是常数。例如：a = 2^n
  • a < 1
最后于 更新