基础概念

循环不变量

• 初始化
• 维护
• 终止

渐进记号

• $\Theta (g(n))$ 渐进紧界
• $O(g(n))$ 渐进上界
• $\Omega (g(n))$ 渐进下界
• $o(g(n))$ 渐进可忽略不计
• $\omega (g(n))$ 渐进主导

NOTE

小 $o$ 和小 $\omega$ 是对任意系数 $c$ 都有相应的性质。

循环不变量

1. Initialization：在第一次循环之前是对的
2. Maintenance：下一次循环时也是对的
3. Termination：结束之后，循环不变量可以导出与结论有关的性质

递归式

• 替换法

  1. 猜答案
  2. 用归纳法证明

  遇到根号等不容易处理的，可以换元

• 递归树 展开所有层，然后按照层进行叠加

• 主定理：用来解决 $T(n)=a\cdot T\left(\frac{n}{b}\right)+f(n)$ 形式的递归式，其中 $a⩾1$，$b>1$，并且 $f(n)>0$

  $$\begin{array}{rl}f(n)=O\left(n^{{\log }_{b}a-\epsilon }\right)& ⟹T(n)=\Theta \left(n^{{\log }_{b}a}\right)\\ f(n)=\Theta \left(n^{{\log }_{b}a}{\log }^{k}n\right)& ⟹T(n)=\Theta \left(n^{{\log }_{b}a}{\log }^{k+1}n\right)\\ f(n)=\Omega \left(n^{{\log }_{b}a+\epsilon }\right)& ⟹T(n)=\Theta \left(f(n)\right)\end{array}$$