之前的回答已经很好地定义了循环不变量。

以下是CLRS的作者如何使用循环不变量来证明插入排序的正确性。

插入排序算法(见书):

INSERTION-SORT(A)
    for j ← 2 to length[A]
        do key ← A[j]
        // Insert A[j] into the sorted sequence A[1..j-1].
        i ← j - 1
        while i > 0 and A[i] > key
            do A[i + 1] ← A[i]
            i ← i - 1
        A[i + 1] ← key

循环不变量在这种情况下: 子数组[1到j-1]始终被排序。

现在让我们检查一下，证明这个算法是正确的。

初始化:在第一次迭代j=2之前。所以子数组[1:1]就是要测试的数组。因为它只有一个元素，所以它是有序的。这样不变性就被满足了。

维护:这可以通过在每次迭代后检查不变量来轻松验证。在这种情况下，它被满足了。

终止:这是我们将证明算法正确性的步骤。

当循环结束时，j=n+1。循环不变量再次被满足。这意味着子数组[1到n]应该排序。

这就是我们想用算法做的。因此，我们的算法是正确的。

除了这些不错的答案，我想Jeff Edmonds在《如何思考算法》(How to Think About Algorithms)中举的一个很好的例子可以很好地说明这个概念:

EXAMPLE 1.2.1 "The Find-Max Two-Finger Algorithm" 1) Specifications: An input instance consists of a list L(1..n) of elements. The output consists of an index i such that L(i) has maximum value. If there are multiple entries with this same value, then any one of them is returned. 2) Basic Steps: You decide on the two-finger method. Your right finger runs down the list. 3) Measure of Progress: The measure of progress is how far along the list your right finger is. 4) The Loop Invariant: The loop invariant states that your left finger points to one of the largest entries encountered so far by your right finger. 5) Main Steps: Each iteration, you move your right finger down one entry in the list. If your right finger is now pointing at an entry that is larger then the left finger’s entry, then move your left finger to be with your right finger. 6) Make Progress: You make progress because your right finger moves one entry. 7) Maintain Loop Invariant: You know that the loop invariant has been maintained as follows. For each step, the new left finger element is Max(old left finger element, new element). By the loop invariant, this is Max(Max(shorter list), new element). Mathe- matically, this is Max(longer list). 8) Establishing the Loop Invariant: You initially establish the loop invariant by point- ing both fingers to the first element. 9) Exit Condition: You are done when your right finger has finished traversing the list. 10) Ending: In the end, we know the problem is solved as follows. By the exit condi- tion, your right finger has encountered all of the entries. By the loop invariant, your left finger points at the maximum of these. Return this entry. 11) Termination and Running Time: The time required is some constant times the length of the list. 12) Special Cases: Check what happens when there are multiple entries with the same value or when n = 0 or n = 1. 13) Coding and Implementation Details: ... 14) Formal Proof: The correctness of the algorithm follows from the above steps.

在处理循环和不变量时，有一件事很多人没有马上意识到。他们混淆了循环不变量和循环条件(控制循环终止的条件)。

正如人们指出的那样，循环不变量必须为真

在循环开始之前 在每次循环迭代之前 在循环结束之后

(尽管在循环体期间它可以暂时为假)。另一方面，循环条件在循环结束后必须为false，否则循环将永远不会终止。

因此循环不变量和循环条件必须是不同的条件。

复杂循环不变量的一个很好的例子是用于二分搜索。

bsearch(type A[], type a) {
start = 1, end = length(A)

    while ( start <= end ) {
        mid = floor(start + end / 2)

        if ( A[mid] == a ) return mid
        if ( A[mid] > a ) end = mid - 1
        if ( A[mid] < a ) start = mid + 1

    }
    return -1

}

因此循环条件看起来非常简单——当开始>结束时，循环终止。但是为什么循环是正确的呢?什么是循环不变量来证明它的正确性?

不变量是逻辑语句:

if ( A[mid] == a ) then ( start <= mid <= end )

这句话是逻辑重言——在我们试图证明的特定循环/算法的上下文中，它总是正确的。并且在循环结束后，它提供了关于循环正确性的有用信息。

If we return because we found the element in the array then the statement is clearly true, since if A[mid] == a then a is in the array and mid must be between start and end. And if the loop terminates because start > end then there can be no number such that start <= mid and mid <= end and therefore we know that the statement A[mid] == a must be false. However, as a result the overall logical statement is still true in the null sense. ( In logic the statement if ( false ) then ( something ) is always true. )

那么我说的循环条件在循环结束时必然为假呢?当在数组中找到元素时，循环条件在循环结束时为true !?实际上不是，因为隐含的循环条件实际上是while (A[mid] != A && start <= end)，但我们缩短了实际的测试，因为第一部分是隐含的。这个条件在循环结束后明显为false，而不管循环如何结束。

循环不变量是在循环执行前后为真的断言。

对不起，我没有评论权限。

正如你提到的@Tomas Petricek

另一个较弱的不变式也是成立的，即i >= 0 && i < 10(因为这是连续条件!)”

为什么它是循环不变量?

我希望我没有错，据我理解[1]，循环不变将在循环开始时为真(初始化)，它将在每次迭代(维护)之前和之后为真，它也将在循环结束后为真(终止)。但是在最后一次迭代之后，i变成了10。因此，条件i >= 0 && i < 10变为假值并终止循环。它违反了循环不变量的第三个性质(终止)。

[1] http://www.win.tue.nl/~kbuchin/teaching/JBP030/notebooks/loop-invariants.html

值得注意的是，循环不变量可以帮助迭代算法的设计，因为它被认为是一个断言，表示变量之间的重要关系，在每次迭代开始时和循环结束时，这些关系必须为真。如果这是成立的，计算是在有效的道路上。如果为false，则算法失败。