递归复杂度分析

代换法

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

$$n\lg n+n$$

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

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

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

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

代数变换

递归树

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

---

主方法

$$T(n)=aT\left(\frac{n}{b}\right)+f(n)$$

和 $n^{{\log }_{b}a}$ 比较，哪个大取哪个，一样大就乘个 $\log n$

下面对 f 函数的重要性进行讨论

---

如果存在某个常数 $ϵ>0$ 有

$$f(n)=O(n^{{\log }_{b}a-ϵ})$$

则

$$T(n)=\Theta (n^{{\log }_{b}a})$$

---

若 $f(n)=\Theta (n^{{\log }_{b}a})$

$$T(n)=\Theta (n^{{\log }_{b}a}lgn)$$

---

若某个常数 $ϵ>0$ 有

$$f(n)=\Omega (n^{{\log }_{b}a+ϵ})$$

且对常数 $c<1$，与所有足够大的 n 有

$$af\left(\frac{n}{b}\right)\le cf(n)$$

则

$$T(n)=\Theta (f(n))$$指向原始笔记的链接