阅读经典——《算法导论》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) + Θ(n²) 等等。

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

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

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

主定理

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

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

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

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

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

使用主方法

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

案例1：

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

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

案例2：

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

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

案例3：

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

我们有 a = 3，b = 4，f(n) = nlgn，因此n^log_ba = n^log₄3 = O(n^0.793) 。由于 f(n) = Θ(nlgn) = Ω(n) = Ω(n^0.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) 。

证明主定理

对于主定理的证明并不困难，但为了简化本文的内容，此处不再给出。

思路是画出递归树，并归纳每层结点的代价以及叶子结点的代价，总代价即是各部分代价之和。详细过程可参考《算法导论》4.6节，以及本文文末的参考资料。

参考资料

主定理的证明及应用举例 Focustc