循环不变式

当我们写完程序后，通常会编写测试来检查程序是否产生预期的结果。如果结果和预期一致，则认为程序能正常完成任务。但是有限的测试用例无法保证程序所使用的算法在其他情况下是否仍然得到正确的结果。因此我们需要证明算法的正确性。

循环不变式（loop invariant）是用于证明循环的循环体在程序执行前后都为真的谓词。需要证明循环不变式的三条性质：

• 初始化：循环的第一次迭代之前，循环不变式为真；
• 保持：如果循环的某次迭代之前不变式为真，那么下次迭代之前它仍为真；
• 终止：在循环终止时，不变式为我们提供了一个有用的性质，该性质有助于证明算法是正确的。

证明方法类似于数学归纳法，证明一个基本情况和一个归纳步：

• 基本情况：第一次迭代之前不等式成立；
• 归纳步：证明从一次迭代到下一次迭代，不变式仍然成立。

数学归纳法中的归纳步是无限的，而循环不变式则需要在循环结束时停止「归纳」。我们通过终止时的循环不变式来证明算法的正确性。通常与导致循环终止的条件一起使用循环不变式。

插入排序

排序就是将一个序列的数按大小进行排列，得到一个新的序列，它满足每个元素都不大于相邻的前一个元素。序列从左到右增长，因此右边是「前」，左边是「后」。每次排序的数称为键（key）。

对一个序列中的数进行排序有许多种算法，首先来看插入排序。插入排序通过对序列中的数进行比较交换，将键按其大小插入到相应位置来完成排序任务。插入排序对数组中的数进行原地（in place）排序，任何时候最多有常数个数字存储在数组外。

1
2
3
4
5
6
7
8

def insertion_sort(a: list[int]) -> None:
    for j in range(1, len(a)):
         key = a[j]
         i = j - 1
         while i >= 0 and a[i] > key:
             a[i + 1] = a[i]
             i = i - 1
         a[i + 1] = key

与 a[j] 相比，变量 key 可以让当前要插入的元素更直观。

插入排序的关键在 while 循环。while 循环在已排序的子数组 a[:j] 中从前向后寻找元素插入位置，其判断条件与 key 的大小有关：

• 若 key 不大于子数组的最小元素，那么即使遍历到第一个元素也不会有比它更小的了。因此当 i = -1 时停止 while 循环，在 a[0] 的位置插入 key。
• 若 key 大于子数组的最小元素，那就表示有元素小于它。因此当 a[i] 小于 key 时停止 while 循环，在该元素下一位置 a[i + 1] 插入 key。

算法分析

对算法进行分析就是对算法所需的资源进行预测。其中最重要的度量是时间。

实现算法的程序运行在一个假想的单处理器计算模型 RAM（random-access mathine）上。我们假设 RAM

• 具有真实计算机常见的指令，每条指令所需时间为常量，并且仅按照顺序执行。
• 具有整形和浮点型数据类型，并为数据类型字长设定一个范围。
• 忽略内存层次的问题以简化模型。

在具体分析算法时，需要对输入规模（input size）和运行时间（running time）进行仔细地定义：

• 输入规模：对于如排序或计算离散傅里叶变换，用输入中的项数度量；对于如两个整数相乘，用二进制记号表示输入所需的总位数；对于图等输入，用两个数来描述输入。
• 运行时间：指在特定输入上执行的基本操作数或步数。定义「步」的概念使得算法尽量与机器无关。假设每次执行第 $i$ 行的代码需要常量时间 $c_i$。算法的运行时间就是每条语句的运行时间之和。

根据给定输入规模下输入的不同，算法的执行时间不同，因而存在最佳情况和最坏情况。我们最感兴趣的是最坏情况，因为：

• 算法的最坏情况给出了任何输入的运行时间的一个上界。
• 某些算法经常会出现最坏情况。
• 平均情况的运行时间往往与最坏情况一样差。

平均情况的运行时间依赖于概率分析。通常可假设给定规模的所有输入具有相同的可能性。如果假设不成立，则可能使用随机化算法，对随机的选择进行概率分析来生成期望的运行时间。

算法运行时间的公式往往是一个多项式。我们只考虑多项式中最高次数的项，而忽略低阶项和最高次数项的常量系数。因为算法运行时间的增长率由最高次数项决定。使用 $\Theta$ 记号将插入排序的最坏运行时间记为 $\Theta(n^2)$。对于足够大的输入，高效的算法具有增长量级更低的最坏运行时间。

归并排序

首先定义递归（recursive）算法：算法一次或多次递归地调用自身来解决密切相关的子问题。

分治法（divide-and-conquer）：一些问题可以分成相类似的规模较小的子问题，子问题也可以继续分解为更小的子问题。像这样递归地求解子问题，然后将解合并，从而得到原问题的解。

分治法的三个步骤：

1. 分解（Divide）：分解原问题为子问题；
2. 解决（Conquer）：递归求解子问题，对规模足够小的子问题直接求解；
3. 合并（Combine）：合并子问题的解，得到原问题的解。

归并排序（merge sort）的操作：

1. 分解：将待排序的 $n$ 个元素的序列分解为两个子序列，每个都有 $n/2$ 个元素。
2. 解决：使用归并排序递归地排序两个子序列。
3. 合并：将两个已排序子序列合并得到完成排序的原序列。

归并排序的关键是「合并」这一步，将两个已排序的序列合并。用辅助函数 merge 表示这个过程。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def merge(a: list[int | float], p: int, q: int, r: int) -> None:
    left = a[p : q + 1]
    right = a[q + 1 : r + 1]
    left.append(float('inf'))
    right.append(float('inf'))
    i = j = 0
    
    for k in range(p, r + 1):
        if left[i] <= right[j]:
            a[k] = left[i]
            i += 1
        else:
            a[k] = right[j]
            j += 1

数组 a[p:r] 的子数组 a[p : q + 1] 和 a[q + 1 : r + 1] 都已经完成排序，现在需要将它们合并，使 a[p:r] 有序。其中数组下标 p、q 和 r 满足 $p\leqslant q < r$。

merge 首先将两个子数组复制到 left 和 right 数组中，然后分别添加 float('inf') 到 left 和 right 的末尾，用无限作为哨兵。然后在 for 循环中比较 left 和 right 中元素的大小，按序复制回数组 a[p:r] 中。merge 需要 $\Theta(n)$ 时间，其中 $n = r - p + 1$，表示合并元素的总数。

现在可以将归并排序的三个步骤用函数 merge_sort 来表示了：

1
2
3
4
5
6

def merge_sort(a: list[int | float], p: int, r: int) -> None:
    if p < r:
        q = (p + r) // 2
        merge_sort(a, p, q)
        merge_sort(a, q + 1, r)
        merge(a, p, q, r)

对于子数组的首尾元素的下标，若 $p \geqslant r$，则子数组中只有一个元素，子数组已排序，这是算法的基本情况。其余情况下需要将子数组分解为两个更小的子数组，递归调用 merge_sort 直到基本情况。根据 $p$ 和 $r$ 的奇偶情况分析可得子数组 a[p : q + 1] 包含 $\lceil n / 2 \rceil$ 个元素，子数组 a[q + 1 : r + 1] 包含 $\lfloor n / 2 \rfloor$ 个元素。

然后从基本情况开始合并，一对子数组合并为包含两个子数组所有元素的子数组，接着与类似的子数组合并为更大的子数组，以此类推，直到合并为长度为 $n$ 的数组。

算法包含对自身的递归调用时，可以用递归等式（recurrence equation）或递归式（recurrence）来描述运行时间。通过主定理可以证明归并排序的最坏情况运行时间为 $\Theta(n\ \text{lg}\ n)$。

为了方便起见，将练习 2.3-2 中未使用哨兵的实现也列出。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

def merge(a: list[int], p: int, q: int, r: int) -> None:
    left = a[p : q + 1]
    right = a[q + 1 : r + 1]
    i = j = 0
    k = p

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            a[k] = left[i]
            i += 1
        else:
            a[k] = right[j]
            j += 1
        k += 1

    if j == len(right):
        a[k : r + 1] = left[i:]

        
def merge_sort(a: list[int], p: int, r: int) :
    if p < r:
        q = (p + r) // 2
        merge_sort(a, p, q)
        merge_sort(a, q + 1, r)
        merge(a, p, q, r)