Question

主方法求解递归式

Answer 1

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

<small>（式4-1）</small>

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

但是有了这些递归式还不够，我们需要确切的知道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 2 ) 。

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

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

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

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

案例1：

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

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

案例2：

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

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

案例3：

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

我们有 a = 3，b = 4，f(n) = nlgn，因此n log b a = n log 4 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) 。

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

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

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

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