阅读经典——《算法导论》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)有如下渐进界：
- 若对某个常数 ε>0 有 f(n) = O(nlogba-ε)，则 T(n) = Θ(nlogba) 。
- 若 f(n) = Θ(nlogba)，则 T(n) = Θ(nlogba lgn) 。
- 若对某个常数 ε>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) 。
证明主定理
对于主定理的证明并不困难，但为了简化本文的内容，此处不再给出。
思路是画出递归树，并归纳每层结点的代价以及叶子结点的代价，总代价即是各部分代价之和。详细过程可参考《算法导论》4.6节，以及本文文末的参考资料。
参考资料
主定理的证明及应用举例 Focustc
