声明 本文并不是从教科书上抄下来的，而是笔者自己瞎想的，很可能有错误，请不吝批评指正。不要在答卷的时候使用本文内容，否则得0分之后果自负。另，本文的示例代码的语法使用的是《算法导论》的伪代码语法。
分治法简介
分治法是一种递归求解问题的方法，分为三个步骤：
- 分解：将问题分为若干个子问题。
- 解决：递归地求解每个子问题，直到子问题小到可以直接求解。
- 合并：将每个子问题的解合并成为整个问题的解。
例如我们想实现一个求和算法 SUM(A, p, r)。算法的输入是一个长度为 n 的数组A，以及需要进行求和的起始下标 p 和结束下标 r，算法返回
。伪代码如下
SUM(A, p, r)
1 if p ≥ r
2 then return A[p]
3 else return SUM(A, p, r-1) + A[r]
如果 A = [1,2,3,4]，则 SUM(A,1,4) 将返回 10。
看下面的图示会对算法的运行情况有一个更直观的了解。
|
分解过程 |
合并过程 |
证明分治算法的正确性
循环不变式同样可以用来证明分治算法的正确性。只不过具体操作上稍有不同——我们不是从第一次递归之前开始证明，而是从第一次直接求解（即最后一次递归调用）时开始证明。一般过程为
初始化：在函数直接求解后，循环不变式成立。
保持：先假设函数内部的所有递归调用均满足循环不变式，再证明函数本身返回后，循环不变式仍然成立。
终止：“最外层”的函数调用返回后，算法结果一定是正确的。
证明 SUM(A, p, r) 是正确的
作为一个实例，证明 SUM() 函数的正确性。
首先，给出循环不变式：对于给定的长度为 n (n ≥ 1) 的数组A，对于任意满足 1 ≤ p ≤ r ≤ n 的整数 p 和 r，SUM（A, p, r) 的返回值为。
初始化：当 p = r 时，SUM() 函数会直接返回 A[p]。另， r = p 时，=A[p]。循环不变式成立。
保持：假设 SUM(A, p, r) 内部执行的递归调用 SUM(A, p, r-1) 满足循环不变式，即 SUM(A, p, r-1) 的返回值是
。由于在第3行执行了 return SUM(A, p, r-1) + A[r]，所以SUM(A, p, r) 返回值满足循环不变式。
终止：当“最外层”的 SUM() 函数返回时，返回值一定是，算法是正确的。
一个更为复杂的例子
这是《算法导论》的思考题7-3，STOOGE 排序。
STOOGE-SORT(A, i, j)
1 if A[i] > A[j]
2 then exchange A[i] « A[j]
3 if i+1 ≥ j
4 then return
5 k ¬ ë(j-i+1)/3û # 下取整
6 STOOGE-SORT(A, i, j-k) # 前 2/3
7 STOOGE-SORT(A, i+k, j) # 后 2/3
8 STOOGE-SORT(A, i, j-k) # 再次前 2/3
这是一个号称很厉害的排序算法。说它厉害并不是因为它有多么的快，事实上它比插入排序还要慢。它的厉害之处在于，用一般的掰手指头的方法绝对无法证明它的正确性。让我们用循环不变式来证明它的正确性。
循环不变式：在每次 STOOGE-SORT(A, i, j) 返回时，数组 A[i..j] 是有序的。
初始化：当 i+1 ≥ j 时，不再进行递归，函数会立即返回。由于执行了第1、2行，可保证 A[i] ≤ A[j]。因为 i+1=j，所以数组A[i..j]有序。循环不变式成立。
保持：假设 STOOGE-SORT(A, i, j) 内部对STOOGE-SORT() 的所有递归调用都满足循环不变式，即STOOGE-SORT(A, i, j-k) 可使 A[i..j-k] 有序，STOOGE-SORT(A, i+k, j) 可使 A[i+k..j] 有序。
∵ k = ë(j-i+1)/3û
∴ j-i+1 ≥ 3k
∴ (j-i+1)-2k ≥ k
∵ A[i..j-k] 与 A[i+k..j] 重叠的部分为 A[i+k..j-k]，共(j-k)-(i+k)+1 = (j-k+1) - 2k ≥ k 个元素
而 A[i..j-k] 与 A[i+k..j] 不重叠的部分为 A[j-k+1..j] 共 j-(j-k+1)+1 = k 个元素。即，A[i..j-k] 与 A[i+k..j] 重叠部分的元素个数大于等于不重叠部分的元素个数。
∴ 在执行了第 6、7 行的STOOGE-SORT(A, i, j-k) 和 STOOGE-SORT(A, i+k, j)，分别使A[i..j-k] 和 A[i+k..j]有序后，可保证 A[j-k+1..j] 中的元素是 A[i..j] 中最大的 k 个元素，且是有序的。
∵ 在执行了第8行的STOOGE-SORT(A, i, j-k)后，可保证 A[i..j-k] 有序。
∴ 综上，可保证在 STOOGE-SORT(A, i, j) 返回后，A[i..j] 是有序的。循环不变式成立。
终止：在最外层的 STOOGE-SORT(A, 1, n) 返回后，可使数组 A 有序，算法是正确的。
证毕