循环不变式（Loop-Invariant）

• 证明排序算法的正确性

• 算法主体是循环

• 归纳证明：
1. Initialization： 算法的初次迭代结果是正确的
2. Maintenance：若上一次迭代的结果是正确的，则此次迭代结果仍是正确的
3. Termination：当循环终止，该不变式可证明此算的正确性

RAM模型（Random-Access Machine）

算法时间复杂度的关注

• 时间消耗T(n)

• n→∞过程中，计算时间的增长率

• 渐进分析：关注最高次项

• 关注最坏情况

• 降低排序算法的开销：降低比较次数

分支（Divide & Conquer）

• 解决问题的一种通用方法

• 过程：
1. 将大问题差分为子问题
2. 攻克子问题（逻辑上递归）
3. 结合解决子问题的子方法，解决大问题

• 举例：归并排序

计算递归时间复杂度的方法

替换法

1. 猜测表达式

2. 归纳证明

3. 根据常数值求解

递归树

• 非正式，快速评估

• 假设每个子问题的规模都是相同的

主定理

• 形式：

• 三种情形：
1. T(root)>T(leave)
树根开销比叶子大



从树根到叶子，每层的开销等比递减
2. T(root)<T(leave)
树根开销比叶子小



3. T(root)=T(leave)
树根和叶子的开销一样



• 总结