算法分析笔记二 -- 递归式

算法分析复习笔记二 -- 递归式

方法一·代换法：

1.猜测解的形式
2.用数学归纳法找出使解真正有效的常数

一些技巧：

1.先证明递归式的较松的上下界，然后再缩小不确定性区间
2.对于无法证明其准确的界时，可以去掉一个低阶项来修改所猜的界

一些陷阱：

拓展 -- 改变变量：

方法二·递归树：

以下图中的递归式为例子：

树高的计算：

复杂度计算：

方法三·主方法定理：

例子：