算法导论
What are algorithms?
非形式地说，算法就是任何良定义（well-defined）的计算过程，该过程取某个值或值的集合作为输入（input），并产生某个值或者值的集合作为输出（output）。
- 算法就是把输入转换成输出的计算步骤。
- 在计算机科学中，算法是使用计算机解一类问题的精确、有效方法的代名词；
- 算法是一组有穷的规则，它规定了解决某一特定类型问题 的一系列运算。 （选自《计算机算法基础》）
- 算法由运算组成
- 算术运算、逻辑运算、关系运算、赋值运算、过程调用
- 算法有其特殊性
- 解决不同问题的算法是不相同的，没有万能的算法
- 算法是有穷的计算过程
- 静态上：规则/运算/语句的数量有穷
- 动态上：计算过程/计算时间有限
作为一种技术的算法
- 算法不仅强调其正确性
- 算法也有好坏之分
- 效率（Efficiency）对于算法的有效性有非常重要的影响。
- 现实应用中，时间和空间都是有限的资源，因此我们应选择时间和空间方面有效的算法来求解问题
算法基础
循环不变式
INSERTION-SORT 的for循环中，循环变量为j（j代表当前正要被插入到
序列中的元素的下标）。循环过程具有以下性质：
子数组A[1~j-1]是已经被排好序的子序列。
这一性质，在j被赋予初值2，首次进入循环之前成立，而且每次循环之
后（j加了1）、进入下一次循环之前也成立。
——把这种在第一次进入循环之前成立、每次循环之后还成立的关系称为“循环不变式”或“循环不变性质” 。
- 插入排序for循环的循环不变式可以描述为：在第1~8行的for循环的每次迭代开始时，子数组A[1~j-1]由原来在 A[1~j-1]中的元素组成，且已按序排列。
可以利用循环不变关系证明循环的正确性。
分三步走：
1）初始化：证明初始状态时循环不变式成立，即证明循环不变式在循 环开始之前为真；
2）保持：证明每次循环之后、下一次循环开始之前循环不变式仍为真；
3）终止：证明循环可以在有限次循环之后终止。
证明循环正确性的思路：
第1）和2）步类似于数学归纳法的证明策略
第3）步保证算法可以终止
如果1）~3）都满足，则说明循环过程正确