杭州交通信息网罗马的假日 韩国:什么是循环不变式
来源：百度文库 编辑：杭州交通信息网 时间：2024/05/05 10:05:51
我最近在看《Accelerated C++》。第二章有一个概念，叫循环不变式。可能是翻译的问题。觉得书中没有讲清楚。谁能给我解释一下什么是循环不变式，有什么用？谢谢！
算法导论第二章中的原文是：We state these properties of A[1 ‥ j -1] formally as a loop invariant。其中举的例子是 插入排序，每次循环从数组A中取出第j个元素插入有序区A[1 .. j-1]，然后递增j。这样A[1 .. j-1]的有序性始终得到保持，这就是所谓的“循环不变”了。
1. 初始化（循环第一次迭代之前）的时候， A[1 ‥ j -1]的“有序性”是成立的；
2. 在循环的每次迭代过程中， A[1 ‥ j -1]的“有序性”仍然保持；
3. 循环结束的时候， A[1 ‥ j -1]的“有序性”仍然成立。
请参考：
http://162.105.69.120/teachers/zhangnx/articals/invariant.txt