循环不变式（Loop-Invariant）

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

RAM模型（Random-Access Machine）

基于RAM模型，算法在渐近分析框架下的计算时间，取决于算法执行过程中基本操作的执行次数。

算法时间复杂度的关注

• 时间消耗T(n)
• n→∞过程中，计算时间的增长率
• 渐进分析：关注最高次项
• 关注最坏情况
• 降低排序算法的开销：降低比较次数

分支（Divide & Conquer）

• 解决问题的一种通用方法
• 过程：
  1. 将大问题差分为子问题
  2. 攻克子问题（逻辑上递归）
  3. 结合解决子问题的子方法，解决大问题
• 举例：归并排序

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

替换法

1. 猜测表达式