1回答

liuyubobobo

2020-08-17

已采纳

循环不变量就是在循环中算法要维持的性质。不同的算法，循环不变量的定义不同，循环不变量是根据自己要写的逻辑自己定义出来的。我们不是先定义循环不变量，再设计算法；而是先设计算法，再定义的循环不变量。

如果你并没有定义循环不变量，就写出了正确的算法，那么对于这个算法来说，定义循环不变量就不是必须。选择排序或许就是这样的例子。其实，因为选择排序太过简单，以至于定义循环不变量根本没有必要。甚至，很多学校的算法课程都不会介绍循环不变量这个概念。在这一小节，我只是先借助选择排序这个简单的算法，介绍循环不变量是什么。

但是，在这个课程的后续，你就会慢慢看到循环不变量的重要性：设计一个算法的思路是一回事儿，准确实现一个算法是另一回事儿。很多时候，循环不变量是算法思想和算法的准确实现之间的桥梁。这一点，或许你在课程后续学习快速排序和二分查找法的时候，会更有体会。

所以，在这里，你可以先大概了解循环不变量的概念：这是在每轮循环开始或者结束的时候，我们的算法整体保持了什么性质。你可以理解成，循环不变量是“算法思想”的细化。选择排序法只是说每次找剩余最小的元素放在前面；通过定义循环不变量，我们就知道了，每轮循环，我们要处理的是 arr[i] 这个元素，我们要再循环中找到 arr[i, n) 中的最小元素，放到 arr[i] 中，从而保证 arr[0, i] 是有序的。同时，循环不变量也帮助我们证明了算法的正确性。

等你学习完快速排序和二分查找法，可以再回头看，看到时候你能不能理解定义清楚循环不变量为什么是重要的。

至于循环不变量的表示方式，也是根据你的算法逻辑来定的。有的算法可能 [0,i) 怎么样；有的算法可能是 (i, n) 怎么样，还有的算法，每轮循环后，处理的数据根本不连续，比如 bfs，那么它是保证找到已经访问过的所有节点的最短距离。

依然是，因为算法设计没有一定之规，循环不变量的定义也就没有一定之规。循环不变量的定义是根据算法的设计而来的。这一点，如果你看完了快速排序和二分搜索后，还有疑问，我们再来讨论。

对于同一个算法，可以有多种定义循环不变量的方式。我们定义的循环不变量不同，有可能写出的代码不同，这一点，我在讲二分搜索的时候，会举一个例子说明。同时，也会有相关的作业，让大家更深入的理解的。

继续加油！：）

8