算法分析复习笔记二 -- 递归式
方法一. 代换法:
1. 猜测解的形式
2. 用数学归纳法找出使解真正有效的常数
一些技巧:
1. 先证明递归式的较松的上下界, 然后再缩小不确定性区间
2. 对于无法证明其准确的界时, 可以去掉一个低阶项来修改所猜的界
一些陷阱:
拓展 -- 改变变量:
方法二. 递归树:
以下图中的递归式为例子:
树高的计算:
复杂度计算:
方法三. 主方法定理:
例子:
来源: http://www.bubuko.com/infodetail-3076299.html