CLRS 算法导论

初始化：循环第一次迭代之前，它为真

保持：如果某次迭代之前它为真，那么下次迭代之前仍为真

终止：循环终止时，不变式有其性质助于证明算法正确

分解原问题为若干规模较小实例的子问题

解决子问题，递归求解子问题，直到子问题足够小时直接求解

合并子问题的解，成为原问题的解

增长量为 $\Theta(n\lg n)$

最坏$\Theta(n^2)$

$\Theta(g(n)) := \{\;f(n): \exists c_1 \exists c_2 \exists n_0(\; \forall n\geqslant n_0 \Rightarrow 0 \leqslant c_1 g(n) \leqslant f(n) \leqslant c_2 g(n) \;) \;\}$

$\Theta$ 记号渐近地给出一个函数的上界与下界

对任意多项式 $p(n)=\sum_{i=0}^d a_i n^i$ 可证 $p(n)=\Theta(n^d)$

$O(g(n)) := \{\; f(n): \exists c \exists n_0 (\; \forall n\geqslant n_0 \Rightarrow 0 \leqslant f(n) \leqslant c g(n) \;) \;\}$

显然 $\Theta(g(n)) \subseteq O(g(n))$

$\Omega(g(n)) := \{\;f(n): \exists c \exists n_0 (\; \forall n\geqslant n_0 \Rightarrow 0 \leqslant c g(n) \leqslant f(n) \;) \;\}$

传递性: $f(n)=\Theta(g(n)) \land g(n)=\Theta(h(n)) \;\Longrightarrow\; f(n)=\Theta(h(n))$

自反性: $f(n)=\Theta(f(n))$

对称性: $f(n)=\Theta(g(n)) \iff g(n)=\Theta(f(n))$

转置对称性 : $f(n)=O(g(n)) \iff g(n)=\Omega(f(n))$