主方法

转自 https://www.jianshu.com/p/4d0b005782d9

阅读经典——《算法导论》04

在算法分析中,我们通常会得到一个关于输入规模n的递归式,形式如下:

<small>(式4-1)</small>

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

例如,归并排序递归式 T(n) = 2T(n/2) + cn ,Strassen算法递归式 T(n) = 7T(n/2) + Θ(n2) 等等。

但是有了这些递归式还不够,我们需要确切的知道T(n)到底是多少,它与n的关系如何。

因此,本文讲述一种求解上述形式的递归式的一般方法,称为主方法。该方法简单易行,通常不需要借助纸笔演算。

递归式(4-1)描述的是这样一种算法的运行时间:它将规模为n的问题分解为a个子问题,每个子问题规模为n/b,其中a和b都是正常数。a个子问题递归地进行求解,每个花费时间T(n/b)。函数f(n)包含了问题分解和子问题解合并的代价。例如,描述Strassen算法的递归式中,a=7,b=2,f(n) = Θ(n2) 。

主定理

下面给出主方法所依赖的定理。

定理4.1(主定理) 令 a≥1 和 b>1 是常数,f(n) 是一个函数,T(n) 是定义在非负整数上的递归式:
T(n) = aT(n/b) + f(n)
那么T(n)有如下渐进界:

  1. 若对某个常数 ε>0 有 f(n) = O(nlogba-ε),则 T(n) = Θ(nlogba) 。
  2. 若 f(n) = Θ(nlogba),则 T(n) = Θ(nlogba lgn) 。
  3. 若对某个常数 ε>0 有 f(n) = Ω(nlogba+ε),且对某个常数 c<1 和所有足够大的 n 有 af(n/b) ≤ cf(n),则 T(n) = Θ(f(n)) 。

让我们尝试了解主定理的含义。对于三种情况,我们都将函数 f(n) 与函数 nlogba 进行比较。直觉上,递归式的解取决于两个函数中的较大者。如情况一是 nlogba 较大,情况3是 f(n) 较大。而情况2是两者一样大,这种情况需要乘上一个对数因子。

需要注意的是,两个函数比较大小时必须确保多项式意义上的小于,也就是说,两者必须相差一个因子 nε,其中 ε 是大于0的常数。另外情况3还需要满足一个额外的条件。

使用主方法

举几个例子就能很容易说明如何使用主方法。

案例1:

T(n) = 9T(n/3) + n

对于这个递归式,我们有 a = 9,b = 3, f(n) = n,因此 nlogba = nlog39 = Θ(n2) 。而 f(n) = n 渐进小于 Θ(n2),所以可以应用于主定理的情况1,从而得到解 T(n) = Θ(n2) 。

案例2:

T(n) = T(2n/3) + 1

其中,a = 1, b = 3/2, f(n) = 1,因此 nlogba = nlog3/21 = n0 = 1 。由于 f(n) = Θ(1) ,与Θ(nlogba)恰好相等,可应用于情况2,从而得到解 T(n) = Θ(lgn) 。

案例3:

T(n) = 3T(n/4) + nlgn

我们有 a = 3,b = 4,f(n) = nlgn,因此nlogba = nlog43 = O(n0.793) 。由于 f(n) = Θ(nlgn) = Ω(n) = Ω(n0.793+0.207),因此可以考虑应用于情况3,其中 ε = 0.207。但需要检查是否满足条件:当 n 足够大时,存在 c<1 使 af(n/b) ≤ cf(n) 。

  • 令 3f(n/4) ≤ cf(n) 有
    3n/4lg(n/4) ≤ cnlgn
    3/4(lgn - lg4) ≤ clgn
    (3/4 - c)lgn ≤ 3/4lg4

容易发现,当 c ≥ 3/4 时,上式对于足够大的 n 恒成立。因此可以使用主定理的情况3,得出递归式的解为 T(n) = Θ(nlgn) 。



作者:金戈大王
链接:https://www.jianshu.com/p/4d0b005782d9
來源:简书

上一篇:算法导论 思考题6-2


下一篇:python 解析字节码的相关方法