====== CLRS 算法导论 ======

===== 第一部分 基础知识 =====

==== 2.1 插入排序 INSERTION-SORT ====
  * **循环不变式**，三条性质：
    * **初始化**：循环第一次迭代之前，它为真
    * **保持**：如果某次迭代之前它为真，那么下次迭代之前仍为真
    * **终止**：循环终止时，不变式有其性质助于证明算法正确
==== 2.2 分析算法 ====
  * 通常集中于只求**最坏**情况运行时间，除了**随机化算法**
  * 感兴趣的是运行时间的**增长率**或**增长量级**
  * 插入排序增长率为 \(\Theta(n^2)\)
==== 2.3 设计算法 ====
  * 分治法：
    * **分解**原问题为若干规模较小实例的子问题
    * **解决**子问题，递归求解子问题，直到子问题足够小时直接求解
    * **合并**子问题的解，成为原问题的解
  * 归并排序 MERGE-SORT
    * 增长量为 \(\Theta(n\lg n)\)
  * 思考题2-2 冒泡排序 BUBBLE-SORT 
    * 最坏\(\Theta(n^2)\)

==== 3.1 渐近记号 ====
  * 渐近紧确界(asymptotically tight bound)
  * \(\Theta(g(n))\) 表示以下函数的**集合**
    * \(\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\) 记号
    * \(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\) 记号只推一个函数的**渐近下界**
    * \(\Omega(g(n)) := \{\;f(n): \exists c \exists n_0 (\; \forall n\geqslant n_0 \Rightarrow 0 \leqslant c g(n) \leqslant f(n) \;) \;\} \)
  * **定理**3.1 对任意两个函数 \( f(n)\) 与 \( g(n) \), 有 \[ f(n)=\Theta(g(n)) \iff f(n)=O(g(n)) \land f(n)=\Omega(g(n)) \]
  * \( o \) 记号表示非紧确上界
  * \( \omega \) 记号表示非紧确下界
  * 渐近比较的关系性质，假定 \(f(n)\) 和  \(g(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))\)