主定理
提示
- 主定理定义:主定理是一个用于快速计算分治算法递归关系式时间复杂度的公式,适用于形式为
T(n) = aT(n/b) + f(n)
的递归关系。 - 递归关系条件:在主定理中,
a
代表递归中子问题的数量,n/b
是每个子问题的大小,f(n)
是递归调用外的工作成本,且a ≥ 1
,b > 1
。 - 时间复杂度计算:根据
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 是一个常数。
以上每个条件可以解释为:
- 如果在每个级别解决子问题的成本增加了一定的因子,
f(n)
的值将比nlogb a
小多项式级别。因此,时间复杂度受最后一级的成本即nlogb a
压制。 - 如果在每个级别解决子问题的成本几乎相等,那么
f(n)
的值将是nlogb a
。因此,时间复杂度将是f(n)
乘以总级别数即nlogb a * log n
。 - 如果在每个级别解决子问题的成本减少了一定的因子,
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