Keep Thriving https://wiki.joak.org/ 2026-04-19T06:49:19+00:00 https://wiki.joak.org/ https://wiki.joak.org/_media/favicon.ico text/html 2019-08-20T04:00:25+00:00 Anonymous (anonymous@undisclosed.example.com) https://wiki.joak.org/public:cs:algorithm:clrs?rev=1566273625&do=diff CLRS 算法导论 第一部分 基础知识 2.1 插入排序 INSERTION-SORT * 循环不变式，三条性质： * 初始化：循环第一次迭代之前，它为真 * 保持：如果某次迭代之前它为真，那么下次迭代之前仍为真\(\Theta(n^2)\)\(\Theta(n\lg n)\)\(\Theta(n^2)\)\(\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…