算法导论

算法基础

循环不变式

• 初始化：循环第一次迭代前，不变式为真；
• 保持：如果循环的某次迭代前不变式为真，那么下次迭代前它仍为真；
• 终止：循环终止时，不变式的性质有助于证明算法的正确性。

渐进记号

• 渐进紧确界：\(\Theta(g(n))=\{f(n)\mid\)存在正常量\(c_1,c_2,n_0\)，使得对所有\(n\ge n_0\)，有\(0\le c_1g(n)\le f(n)\le c_2g(n)\}\)；
• 渐进上界：\(O(g(n))=\{f(n)\mid\)存在正常量\(c,n_0\)，使得对所有\(n\ge n_0\)，有\(0\le f(n)\le cg(n)\}\)；
• 渐进下界：\(\Omega(g(n))=\{f(n)\mid\)存在正常量\(c,n_0\)，使得对所有\(n\ge n_0\)，有\(0\le cg(n)\le f(n)\}\)。

求解递归式

代入法

• 猜测解的形式；
• 用数学归纳法证明解的正确性。

递归树法

• 画出递归树；
• 求解每一层的代价；
• 对所有层的代价求和。

主定理法

令\(a\ge1\)和\(b>1\)是常数，\(f(n)\)是一个函数，\(T(n)\)是定义在非负整数上的递归式： \[ T(n)=aT(\frac{n}{b})+f(n) \] 那么\(T(n)\)有如下渐进界：

• 若对某个常数\(\varepsilon>0\)有\(f(n)=O(n^{\log_ba-\varepsilon})\)，则\(T(n)=\Theta(n^{\log_ba})\)；
• 若\(f(n)=\Theta(n^{\log_ba})\)，则\(T(n)=\Theta(n^{\log_ba}\lg n)\)；
• 若对某个常数\(\varepsilon>0\)有\(f(n)=\Omega(n^{\log_ba+\varepsilon})\)，且对某个常数\(c<1\)和所有足够大的\(n\)有\(af(n/b)\le cf(n)，\)则\(T(n)=\Theta(f(n))\)。

简单来说即比较\(f(n)\)与\(n^{\log_ba}\)的值：若\(n^{\log_ba}\)更大，则对应情况1；若\(f(n)\)更大，则对应情况3；若大小相当，则乘上一个对数因子，对应情况2。

另外这三种情况并未覆盖\(f(n)\)的所有可能性，情况1和2、2和3之间有一定间隙。

分治算法