数据结构与算法 / 系统课时

循环不变式

循环不变式

循环不变式是在指定的迭代检查点持续成立的性质。它描述目前已经处理到哪里以及这一部分满足什么条件。要证明整个算法正确,还要说明退出时为何得到后置条件,以及循环为何会退出。 MIT《计算机科学的数学》不变式资料

学习目标

  • 写出检查点、循环条件、不变式和后置条件。
  • 用初始化与保持证明退出时的结果性质,并给出终止理由。
  • 对插入排序同时证明非递减、元素守恒和原输入保持不变。

四个检查点

  1. 初始化。 首次检查循环条件前,不变式成立,即使循环体一次都不会执行。
  2. 保持。 假设某轮开始前不变式和循环条件成立,证明执行一轮后不变式仍成立。
  3. 退出推出结果。 把不变式与循环条件为假结合,得到目标后置条件。
  4. 证明终止。 找一个每轮严格下降且有下界的整数,或给出等价的有限步理由。只有退出推导只能说明若终止就正确。

循环不变式三步证明关系图

插入排序的外层不变式

给定整数列表,排序返回新列表,要求按非递减顺序包含原来每个元素和它的出现次数。先复制输入,把 j 定义为已处理前缀的长度。每次检查外层条件前,满足 0 ≤ j ≤ n,a[:j] 已按非递减顺序排列,且与原始输入的前 j 个元素有相同的多重集合。后缀 a[j:] 仍与原输入对应后缀相同。 MIT 插入排序课程资料

  • 初始化。 j=min(1,n)。空前缀或单元素前缀已排序,复制后元素和后缀都匹配。
  • 保持。 保存 key=a[j]。从有序前缀的右端向左,把连续大于 key 的元素右移一个位置。当左侧为空或遇到不大于 key 的元素时,将 key 放在空位。插入点两侧保持顺序,保存的 key 加回后元素守恒;暂时的重复位置只发生在内部右移时。下一段后缀不受影响,令 j←j+1 后外层不变式仍成立。
  • 退出。 外层条件 j<n 不成立时,由 j≤n 得 j=n。已排序前缀覆盖整个输出,元素次数保持不变。
  • 终止。 外层剩余量 n-j 每轮减 1。内层索引 i 每次右移后也减 1,降到 −1 后短路停止,不会读 a[-1]。

用断言检查状态

把下面程序保存为 insertion_sort_demo.py,使用 Python 3.11 或以上运行。可选检查在外层迭代边界验证有序、元素次数及后缀。它用于调试样例。Python 可在优化模式关闭断言,且这里的切片、计数和排序会增加执行成本,性能实验应关闭检查。 Python Counter 多重集合接口

python
from collections import Counter


def insertion_sort(values: list[int], *, check: bool = False) -> list[int]:
    a = values.copy()
    n = len(a)
    j = min(1, n)
    while True:
        if check:
            assert 0 <= j <= n
            assert a[:j] == sorted(a[:j])
            assert Counter(a[:j]) == Counter(values[:j])
            assert a[j:] == values[j:]
        if j == n:
            return a

        key = a[j]
        i = j - 1
        while i >= 0 and a[i] > key:
            a[i + 1] = a[i]
            i -= 1
        a[i + 1] = key
        j += 1


if __name__ == "__main__":
    data = [5, 2, 4, 6, 1, 3, 2]
    print("原始数组:", data)
    print("排序结果:", insertion_sort(data, check=True))
    assert insertion_sort([], check=True) == []
text
原始数组: [5, 2, 4, 6, 1, 3, 2]
排序结果: [1, 2, 2, 3, 4, 5, 6]

程序用 while True 加返回实现每次先做检查再判断退出,j==n 正好对应证明中 j<n 为假。关闭检查时,逆序且各值不同的输入需要移动 1+2+…+(n−1)1+2+…+(n-1) 次;复制的输出列表占用随输入长度增长的空间。不要把调试模式中的额外切片或排序开销计入核心步骤。 MIT 插入排序课程资料

本课练习

给非空列表的最大值扫描写出前缀不变式与剩余量。再暂时注释排序中插回 key 的赋值语句,用 [2,1] 观察有序检查与元素次数检查哪个发现问题。下一章从输入规模和基本操作开始分析算法成本。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

循环不变式

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通