public:cs:algorithm:clrs

CLRS 算法导论

  • 循环不变式,三条性质:
    • 初始化:循环第一次迭代之前,它为真
    • 保持:如果某次迭代之前它为真,那么下次迭代之前仍为真
    • 终止:循环终止时,不变式有其性质助于证明算法正确
  • 通常集中于只求最坏情况运行时间,除了随机化算法
  • 感兴趣的是运行时间的增长率增长量级
  • 插入排序增长率为 \(\Theta(n^2)\)
  • 分治法:
    • 分解原问题为若干规模较小实例的子问题
    • 解决子问题,递归求解子问题,直到子问题足够小时直接求解
    • 合并子问题的解,成为原问题的解
  • 归并排序 MERGE-SORT
    • 增长量为 \(\Theta(n\lg n)\)
  • 思考题2-2 冒泡排序 BUBBLE-SORT
    • 最坏\(\Theta(n^2)\)
  • 渐近紧确界(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))\)
  • public/cs/algorithm/clrs.txt
  • 最后更改: 2019/08/20 12:00
  • oakfire