# 循环不变量简介

# 视频教程

建议快进播放。

「循环不变量」不是很难懂，不是很高深的概念，其实很多时候已经隐藏在我们编码的过程中。

其实我们不知道「循环不变量」，照样可以把代码写对。有一些朋友不一定看过《算法导论》，但并不影响这些朋友能够顺利地解答算法问题），因为 写代码的过程中遵守不变的性质是一件顺利成章、非常自然的事情，这是我们大家心里都有的概念。把这种自然而然的事情起一个名字，叫做遵守了「循环不变量」。

循环不变量即：在循环开始之前、循环的过程中、循环结束以后，变量的定义保持不变，也可以简单地理解为：保持定义不变。这里的「定义」是什么？是我们根据需要解决的问题自行设置的定义。这是一条非常基本的编程准则。

为了完成一件事情，我们需要设计若干个变量。在循环的过程中，变量的值是变化的，在变化中保持不变的性质就称为循环不变量。这里的「量」指的是一些可以判断真假的语句，是我们根据问题的要求和目标人为定义的。定义了不同的循环不变量，对应了不同的算法细节。

《算法导论（第 3 版）》对于循环不变量的描述是这样的：

循环不变式主要用来帮助我们理解算法的正确性。关于循环不变式，我们必须证明三条性质：

初始化：循环的第一次迭代之前，它为真。

保持：如果循环的某次迭代之前它为真，那么下次迭代之前它仍为真。

终止：在循环终止时，不变式为我们提供一个有用的性质，该性质有助于证明算法是正确的。

我的解释：

「初始化」指的是循环开始前，我们什么都没有做的时候；
「保持」指的是在循环的过程中，我们一点一点维护了一件事情；
「终止」指的是循环结束的时候，由「初始化」和「保持」逐步递推，循环不变的范围逐步扩大（例如排序，让有序排序范围逐步扩大）或者逐步缩小（例如查找，搜索范围逐渐减少）或者是变化（例如滑动窗口问题）的，直到完成任务。

「初始化」和「保持」是原因，「终止」是结果。

在《算法导论（第 3 版）》里，很多地方都出现了「循环不变量」，它们是：插入排序、归并排序、优先队列、最小生成树、单源最短路径。

作者：liweiwei1419 链接：https://suanfa8.com/loop-invariant 来源：算法吧著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。