2. 算法基础

本章介绍了一个证明算法正确性的方法——循环不变式，对算法运行时间的简单分析，以及分治法。

循环不变式

类似于数学归纳法的一种证明算法正确性的方法。
需要证明以下三步：

• 初始化
  循环的第一次迭代前，它为真。
• 保持
  如果循环的某次迭代之前它为真，那么下次迭代之前它仍为真。
• 终止
  再循环终止时，不变式为我们提供一个有用的性质，该性质有助于证明算法是正确的。

分治法

将原问题分解为几个规模较小但类似于原问题的子问题，递归求解这些子问题，然后合并这些子问题的解来建立原问题的解。
每层递归时，都有如下三个步骤：

• 分解
  将原问题分解为几个规模较小但类似于原问题的子问题
• 解决
  递归求解各个子问题，当子问题规模够小可以直接求解时，则直接求解
• 合并
  合并这些子问题的解来建立原问题的解

涉及算法

点击查看实现

• 插入排序
• 归并排序

习题答案

思考题

• 2-4 逆序对