循环不变式

一、数学归纳法

因为循环不变式的定义与数学归纳法类似，所以我们先来看看数学归纳法。

我们首先从高中开始回忆起，有关于数列的数学归纳法。

一般的，证明一个与正整数 \(n\) 有关的命题，可以分为以下两个步骤^[1]：
1. 归纳奠基：证明当 \(n=n_0 (n_0 \in N^*)\) 时，命题成立。
2. 归纳步骤：证明当 \(n=k (k \in N^*, k \geq n_0)\) 时，命题成立，证明当 \(n=k+1\) 时，命题也成立。
根据 1. 2. 两步，我们可以断定对于 \(n_0\) 之后的所有正整数 \(n\)，命题都成立。
对于上述的证明过程，我们称之为数学归纳法。

二、循环不变式

《算法导论》有关于循环不变式的定义^[2]：

循环不变式主要用来帮助我们理解算法的正确性。关于循环不变式，我们必须证明三个性质：
1. 初始化：循环的第一次迭代之前，它为真。
2. 保持：如果循环的某次迭代之前它为真，那么下次迭代之前它仍为真。
3. 终止：在循环终止时，不变式为我们提供一个有用的性质，该性质有助于证明算法是正确的。

基于霍尔三元组的定义，我们可以将循环不变式中while的部分正确性可定义为^[3]：

\[\frac{ \{ C \wedge I \} \text{ body } \{I\}}{\{I\} \textbf{ while } (C) \text{ body } \{ \neg C \wedge I \}} \]

当前两条性质成立时，在循环的每次迭代之前，循环不变式都为真。（当然，为了证明循环不变式在每次迭代之前保持为真，我们完全可是使用不同于循环不变式本身的其他已证实的事实。）注意，这类似于数学归纳法，其中为了证明某条性质成立，需要证明一个基本情况和一个归纳步骤。这里，证明第一个迭代之前不变式成立对应于基本情况，证明从一次迭代到下一次迭代不变式成立对应于归纳步骤^[2:1]。

第三条性质也是是最重要的，因为我们将使用循环不变式来证明正确性。通常，我们和导致循环终止的条件一起使用循环不变式。终止性不同于我们通常使用数学归纳法的做法，在归纳法中，归纳步是无限地使用得，这里当循环终止时，停止“归纳”^[2:2]。

下面通过两个例子来说明循环不变式的使用。

三、循环不变式的使用

3.1 线性查找

本部分内容参考自知乎专栏《算法导论》——循环不变式^[4]。

我们首先来看一个简单的例子，线性查找。线性查找的算法如下：

int LinearSearch(int A[], int n, int x)
{
    for (int i = 0; i < n; i++)
    {
        if (A[i] == x)
            return i;
    }
    return -1;
}

我们来证明这个算法的正确性。首先我们需要定义循环不变式，这里我们定义循环不变式为：

在每次迭代之前，如果 \(x\) 在 \(A[0..i-1]\) 中，则 \(A[0..i-1]\) 中的元素都不等于 \(x\)。

接下来我们证明循环不变式的三条性质：

1. 初始化：在第一次迭代之前，\(i = -1\)，所以 \(A[0..i-1]\) 为空，因此循环不变式成立。
2. 保持：在第 \(k\) 次迭代之前，在数组 \(A[0..k-1]\) 中找不到 \(x\)，所以 \(A[0..k-1]\) 中的元素都不等于 \(x\)，因此循环不变式成立。
3. 终止：
   1. 在第 \(n\) 次迭代时，找到了 \(x\)，所以 \(A[0..n-2]\) 中的元素都不等于 \(x\)，因此循环不变式成立。
      • 更为详细的，
      • I. 在第 \(n\) 次迭代时，找到了 \(x\)，所以对于 \(i = n - 1\) 时，\(A[0..i-1]\) 中的元素都不等于 \(x\)。则有 \(A[0..n-2]\) 中的元素都不等于 \(x\)。
      • II. \(\forall{k}\in{[0,i)}\), 由 2. 保持 ，所以 \(A[k] \neq x\) 。
   2. 在第 \(n\) 次迭代时，没有找到 \(x\)，所以 \(A[0..n-1]\) 中的元素都不等于 \(x\)，因此循环不变式成立。
      综上所述，循环不变式成立，算法正确。

3.2 插入排序

插入排序是个比较经典的排序算法，其算法过程为：

1. 将第一个元素看作已排序的序列，将第二个元素到最后一个元素看作未排序的序列。
2. 从未排序的序列中取出第一个元素，将其插入到已排序的序列中的合适位置。
3. 重复步骤 2，直到未排序的序列为空。

通俗来说就是，每次从后面的未排序序列中取出一个元素，然后将其插入到前面的已排序序列中的合适位置。

插入排序的算法如下：

void InsertionSort(int A[], int n)
{
    for (int i = 1; i < n; i++)
    {
        int key = A[i];
        int j = i - 1;
        while (j >= 0 && A[j] > key)
        {
            A[j + 1] = A[j];
            j--;
        }
        A[j + 1] = key;
    }
}

我们来证明这个算法的正确性。首先我们需要定义循环不变式，这里我们定义循环不变式为：

在每次迭代之前，\(A[0..i-1]\) 中的元素都是原来 \(A[0..i-1]\) 中的元素，但已经按序排列。

接下来我们证明循环不变式的三条性质：

1. 初始化：在第一次迭代之前，\(i = 1\)，所以 \(A[0..i-1]\) 只有一个元素，既 \(A[0]\)，对于这一个元素，显然是已经按序排列的，因此循环不变式成立。
2. 保持：对于for循环体的第一行，我们可以看到，每次迭代都会将 \(A[i]\) 的值赋给 \(key\)，所以 \(A[0..i-1]\) 中的元素都是原来 \(A[0..i-1]\) 中的元素，但已经按序排列。接下来我们来看while循环体，while循环体的第一行是 \(A[j + 1] = A[j]\)，这一行的作用是将 \(A[j]\) 的值赋给 \(A[j + 1]\)，这样就将 \(A[j]\) 向后移动了一位。为方便起见，我们统一用 \(i\) 表示，重述上一句话，也就是当第 \(A[i] < A[i - 1]\) 时，将 \(A[i]\) 的值不断向前移动。直到到达一个位置，是的这个移动的值大于前面的值。
   3。 终止：导致for循环结束的条件是 \(i = n\)，那么对于 \(A[0..n-1]\) 中的元素，均根据 2. 保持，已经按序排列，特别的 \(A[0..n-1]\) 中的元素就是数组 \(A\) 的所有元素，因此循环不变式成立，算法正确。

以上就是我对于循环不变式的理解，如果有错误的地方，欢迎指正。

参考与注释：