上一篇算法学习笔记：分治法中，介绍了分治法及一些常见的分治法案例。其中递归式与分治方法是紧密相关的，因为使用递归式可以很自然地刻画分治算法的运行时间。一般来说，求解递归式有“代入法”，“递归树法”和“主方法”。其中主方法用于方便地求解形如$T(n)=aT(n/b)+f(n)$的递归式。

本文将介绍主方法的一个“简化版本”，虽然是简化的，但它依然可以满足日常大多数的算法分析，并且更好理解其含义，最后再给出一个主方法的简要证明过程。

1. 主方法

1.1 定理描述

若算法的运行时间$T(n) \le aT({n \over b}) + O({n^d})$，其中$a \ge 1$是子问题个数，$b \ge 1$是输入规模减小的倍数，$d \ge 0$是递归过程之外的步骤的时间复杂度指数，则：

$$T(n) = \begin{cases} O(n^d \log n) & a = {b^d} \cr O(n^d) & a < {b^d} \cr O({n^{ { {\log }_b }a } }) & a > {b^d} \end{cases}$$

可见主定理有三种情况。例如：

1. 归并排序：$T(n) = 2T({n \over 2}) + O(n), a=2, b=2, d=1$，则$T(n)=O(nlogn)$
2. $T(n) = 2T({n \over 2}) + O({n^2}), a=2, b=2, d=2$，则$T(n)=O({n^2})$
3. Strassen矩阵乘法：$T(n) = 7T({n \over 2}) + O({n^2}), a=7, b=2, d=2$，则$T(n)=O({n^{ { {\log }_2 }7 } })$

1.2 定理证明

考虑下图中的递归树。

1. 递归树的第j层（$j = 0,1, \cdots ,{ {\log }_b}n$），一共有${a^j}$个子问题，
2. 每个子问题的规模是$n/{b^j}$。
3. 对于第j层的1个子问题，递归之外所做的工作不会超过$c \cdot {({n \over { {b^j}}})^d}$
4. 第j层工作量上界为${a^j} \cdot c \cdot {({n \over { {b^j}}})^d} = c{n^d} \cdot {({a \over { {b^d}}})^j}$ ①
5. 所有层总的工作量上界为$c{n^d} \cdot \sum\limits_{j = 0}^{ { {\log }_b}n} { { {({a \over { {b^d}}})}^j}} $ ②

【补充知识：等比数列求和
对于$S = \sum\limits_{i = 0}^k { {r^i}} = { { {r^{k + 1}} - 1} \over {r - 1}}$
当$0 \le r < 1$时，$S \le {1 \over {1 - r}}$，这是一个常量
当$r=1$时，$S=k+1$
当$r>1$时，$S \le {r^k} \cdot (1 + {1 \over {r - 1}})$ 】

对①式的解释：$a$为子问题的增长率（rate of subproblem proliferation, RSP），$b^d$为每个子问题工作量的缩减率（rate of work shrinkage, RWS）

1. 主定理第一种情况：当RSP=RWS时，每一层的工作量不变。此时②=$c{n^d} \cdot ({ { {\log }_b}n} + 1) = O({n^d}\log n)$
2. 主定理第二种情况：当RSP<RWS时，每一层工作量逐渐减少（最大工作量在第0层），总工作量取决于第0层的工作量。注意到②式的求和部分上界为常量，所以②=$O({n^d})$
3. 主定理第三种情况：当RSP>RWS时，每一层工作量逐渐增加（最大工作量在叶子结点）。注意到②式的求和部分上界为$S \le {r^k} \cdot (1 + {1 \over {r - 1}})$，是与k有关的常量，显然最大的常量为$k = {\log _b}n$的时候。

$$ \eqalign{
& ② = O({n^d} \cdot {({a \over { {b^d}}})^{ { {\log }_b}n}})
& = O({n^d} \cdot {a^{ { {\log}_b}n}} \cdot {b^{ {-d} { { {\log }_b}n}}} ) \cr
& = O({n^d} \cdot {a^{ { {\log }_b}n}} \cdot {n^{ - d}}) \cr
& = O({a^{ { {\log}_b}n}}) = O({n^{ { {\log}_b}a}}) \cr} $$

显然${a^{ { {\log}_b}n}}$代表叶子结点数。最后两个等号的转换只要两边同时取对数b即可。QED

总结：通过以上对主定理的简单证明，我们可以更加深入地理解分治法的本质。对于$T(n)=aT(n/b)+O({n^d})$，$a$为子问题的增长率，$b^d$为每个子问题工作量的缩减率，这两者之间的大小将决定算法时间复杂度由哪一部分起更大的主导作用。由于渐近记号会忽略各种低阶项，所以随着递归树层数的深入，当每一层工作量逐渐减少时，顶层原问题占主导地位；当每一层工作量逐渐增加时，底层子问题占主导地位；当每一层工作量都不变时，则要将每层的工作量都加起来。

参考文献：机械工业出版社《算法导论（第3版）》4.5节，4.6节

上一篇：算法学习笔记：快速排序

下一篇：算法学习笔记：分治法