递归复杂度分析

代换法

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

$$n\ln n+n$$

代换法可以确定一个递归式的上界或下界

然后用不等式判断猜测的结论是否成立

有的时候边界条件可能出现不满足我们猜测的界的情况，如 $n=1$ 的时候，可以采用拓展边界条件的方法，只对 $n>n_0$ 的情况进行讨论

有的时候可能是假设不够强导致数学归纳法推理上界的时候不行，所以有时候需要 $-b$ 一下让推理继续进行

代数变换

递归树

统计每一层的代价，分析总的层数，然后求和

---

主方法