Preview
写在前面：决定还是简要讲下这三章。毕竟算法分析和渐进求解也算是我的弱项：P
Keywords： 数学归纳法 分治法 渐进记号
先修知识：
插入排序，冒泡排序和选择排序。这三种排序实在过于简单，简单到除了应试题以外在实际应用中几乎见不到。虽然在数据量较小的时候其实它们是要比归并更快的（毕竟实际的用时不仅仅只考虑Comparison times），但你可能更倾向于用sort方法搞定一切——除非数据量足够小而你仍然要进行优化，那么这个时候请按这些排序的命名自己边猜边写吧。
算法基础
插入排序的正确性证明
1 for index = 2 to array.length {
2 key = array[index]
3 index2 = index – 1
4 while index2 > 0 && array[index2]> key {
5 array[index2 + 1] = array[index2]
6 index2 = index2 - 1}
7 array[index2 + 1] = key}
显而易见地，对于一个近似有序的数据，插入排序的时间复杂度是n，而同为原址排序的快速排序则可能是n^2。这是除了小数据量以外唯一我能想到的插排比快排稳定的时候了。
我们可以简要地证明这个插入排序算法的正确性。
-
初始化：将已经参与排序的数字视为一个额外的数组。把这个额外数组保持有序的性质叫做循环不变式。
-
保持：每次循环时都会进行相应操作，并且带来一个新的元素。对于第一次操作，只有两个数参与，很明显结果会是一个有序的数组，即循环不变式成立。每次加入的新元素都会被插入到一个合适的位置以保证有序，也就是说每一次循环操作后循环不变式都成立。
-
终止：最终结果必然满足循环不变式，即有序。
这个过程本身就是数学归纳法。实际上很多的算法证明都依赖于数学归纳法，比如旅行商问题的分支界限法，以及求解最长公共子序列就需要每次循环之后验证目前的路线是否是局部最优解。往后的算法证明中若有简单的数学归纳法将不再赘述。
分析插入排序算法
一条指令所消耗的时间不一定是常量时间。比如，a^n需要执行乘法n次，而乘法又需要n次加法。值得一提的是，计算2^k对于二进制计算机而言只需要将整数左移就可以在常量时间内得到答案，但在计算前进行if判断显然又会拖累其他可能的计算。
以插入排序为例子来探究算法的分析或许更有意义。上述七行插入排序的算法，每一行可以认为执行一次需要一定的代价(cost)，比如赋值，迭代，比较等等。在while区块之前和之后的语句，每一行执行n级别的次数。在while区块内部的语句，可以认为是循环嵌套，即变相求和，求每一次进入while所执行该行的次数的和。
T(n) = c1n + c2(n-1) + c3(n-1) + c4(求和) + c5(求和) + c6(求和) + c7(n-1)
//cx=第x行的cost，懒得写求和公式了
显然地，当目标无限近似有序时，求和部分变成 n-1， 那么该算法所消耗的时间只取决于 n 的大小和每行的「cost」。当目标无限近似反向有序时，求和部分变成n(n+1)/2-1 以及 n(n-1)/2，那么最坏情况下T(n)将变成n的二次函数，取决于n^2的大小和每行的「cost」。
归并排序的分析
归并排序的伪代码和过程不再赘述。值得一提的是，归并排序是先分后治，分的时候基于递归，而合并的时候基于迭代。迭代的过程又是一种数学归纳法，因此归并排序算法的正确性是可以容易地证明的。分治策略的通用递归式和上下界处理将在第四章和第八章进一步讨论。
full cost = cnlogn + cn的由来，另一个 cn 比较次数就不讨论了
时间复杂度
Θ(g(n)) = {f(n): 存在正常量c1, c2和n0，使得对所有n>=n0， 有0 <= c1g(n) <= f(n) <= c2g(n)}
O(g(n)) = {f(n): 存在正常量c和n0，使得对所有n>=n0，有0 <= f(n) <= cg(n)}
Ω(g(n)) = {f(n): 存在正常量c和n0，使得对所有n>=n0，有0 <= cg(n) <= f(n)}
以上是三种时间复杂度的定义，分别计算渐进紧确界，渐进上界和渐进下界。
渐进记号可以做一些运算。比如2n^2 + Θ(n) = Θ(n^2)
同时它们也满足 symmetric, anti-symmetric, reflexive, transitive——比方说f(n) = Θ(g(n)) 且g(n) = Θ(h(n)) ，可以推出来f(n) = Θ(h(n))，即transitive
如果有f(n) = O(n^k)，那么函数f(n)应该是多项式有界的。渐进上界能够超过n^k的函数有可能是np问题的求解时间函数。显然大O比另外两个都重要。
还有些其他的知识点都在离散数学里，就不赘述了。斐波那契数列的指数增长证明有兴趣可以查一查。
题目答案
前三章的练习题用处不大（大部分都是数学题）
第二章
2.1-4 创立一个额外的n元数组储存是否进位。初始化全为0。计算时按加法定律三个数组相应位置的元素相加。伪代码略
2.2-4 预先判断输入是否满足一些储存的特殊情况，比如之前提到的二进制计算机求2^k的值，只需要把1左移k位。
2.3-4
T(n) =2 if n = 2 or ` T(n-1) + n if n> 2`
2.3-5 伪代码略 对于一个2^n个元素的查找串，二分查找的折叠过程每次将查找串折半。假设目标元素直到剩下最后一个可能元素都没有被找到，那么这个过程「n/2/2/2…=1」执行的次数的复杂度自然是logn 。
2.3-7 先占着
2-1 先占着
第三章
3.1-4 前者成立，后者不成立。这个问题我在学0/1背包问题的时候正好考虑过。显然对于2^(n+1)在证明过程中只要让常数c大于2就行了，而2^(2n)需要让c大于2^n，而2^n又不是常数。这个可以类比成0/1/2/3背包问题。
吐槽：没想到这本书的细节这么多，几乎每一行都可以记成笔记……我已经尽可能把24页的东西缩成4页了。往后简单的概念和证明就干脆不提了，重点还是放在算法的性质，复杂的证明和课后题目上。Anyway，这本书涵盖的东西不是两三个月能写完的……