主定理的证明

算法分析的那个定理.

Master Theorem

where , are constants and is nonnegative. Then

1. If for some constant , then .
2. If , then .
3. If for some constant , and if for some constant and all sufficiently large , then .

直观上看就是比较 与 的阶数, 其中大的决定了 的阶数; 如果阶数相同则乘 .

证明: 先对 为 , 的情形证明, 下面的渐近符号都是对 在 上的点而言的. 写出递归树,

高度为 , 故有 个叶, 从而

其中

Case 1. , 易得 .

Case 2. , 易得 .

Case 3. 首先 . 又 for some constant and sufficiently large . 即 . 得

故 .

对一般的 证明略.

Substitution Method

一个粗糙的方法是 substitution method: 首先猜一个阶, 然后验证这个阶是正确的.

例如对

想验证 , 即存在 和 , 对任意 , 成立 , 代入迭代式,

其中 这一项因为是关于主项 的无穷小项, 所以总是可以想办法消除掉的 (所以可以不管), 例如设

其中 , 则

也就验证了 .

一种错误

若猜测 , 代入 , 则 , 主项的常数对不上, 也就没有证明 .

变量代换

令 ,

再令 .

证明主定理

以 case 1 为例, 先证明 . 易知

主项对上了, 所以 , 反过来易知 .

参考

Leiserson, C. E., Rivest, R. L., Cormen, T. H., & Stein, C. (2009). Introduction to algorithms (3rd ed.). Cambridge, MA: MIT press. pp. 83-106