分治法 · Learning Notes

分治法把问题分成若干同型子问题，分别求解后再合并。它和递归经常一起出现：递归是执行方式，分治是“怎么分、怎么合”的结构。本页给出分治的适用条件，并用寻找最小值、同时求最值、归并排序和二进制加法说明分解与合并如何落地。递归本身的写法见递归；子问题大量重叠时，应改用动态规划。

定义

分治法把复杂问题分解成两个或更多相同或相似的子问题，直到子问题可以简单地直接求解，原问题的解由子问题的解合并而成。一次分治包含三步：

分解：把规模为 $n$ 的实例划分成若干规模更小的同类实例。
求解：对子问题递归使用同一方法；规模足够小时直接求解。
合并：把子问题的解组合成原问题的解。

这三步描述的是算法结构，不是代码模板。有的问题合并只需一次比较，有的问题需要按顺序拼接整段结果；合并方式不同，分治的收益也不同。

适用条件

分治能成立，通常需要同时满足以下条件：

子问题与原问题同型：可以用同一个函数处理，否则只是普通的任务拆分。
子问题相互独立：同一个子问题不会被重复求解。若子问题大量重叠，分治会反复计算同一批状态，应改用动态规划。
规模确实缩小：分解后的每个子问题都严格小于原问题，递归才能终止。
合并的代价可控：如果合并比重新计算还昂贵，分解就没有收益。

与递归、动态规划的关系

分治描述“怎么分解、怎么合并”，递归是常见的实现方式；两者不是同义词。动态规划也常写成递推式，但它会保存子问题的答案。判断时先看子问题是否重叠：重叠就用动态规划，不重叠再考察分治的合并是否划算。

代价的估计

分治不保证更快。寻找最小值无论用循环还是分治，都至少检查每个元素一次；归并排序的收益来自“合并两个有序列表”这一步，代价是 $O(n\log n)$ 的时间和 $O(n)$ 的额外空间。分析时分别估计分解、递归调用和合并的工作量，不要只数递归调用的层数。

例子

寻找最小值：循环扫描

1
def M(a):
2
    m = a[0]
3
    for i in range(1, len(a)):
4
        if a[i] < m:
5
            m = a[i]
6
    return m
7

8

9
a = [4, 1, 3, 5]
10
print(M(a))

循环维护“目前已扫描部分的最小值”，每读入一个元素比较一次。对 $n$ 个元素需要 $n-1$ 次比较。

寻找最小值：线性递归

1
def M(a):
2
    print(a)
3
    if len(a) == 1:
4
        return a[0]
5
    return min(a[len(a) - 1], M(a[0 : len(a) - 1]))
6

7

8
L = [4, 1, 3, 5]
9
print(M(L))

每层把最后一个元素与“前面部分的最小值”比较。print(a) 用来观察每层处理的区间如何缩短，实际使用时可以删除。这个写法仍然是线性递归：每层只调用一次自身，比较次数与循环版相同。

寻找最小值：二分递归

1
def M(a):
2
    if len(a) == 1:
3
        return a[0]
4
    return min(M(a[0 : len(a) // 2]), M(a[len(a) // 2 : len(a)]))
5

6

7
L = [4, 1, 3, 5]
8
print(M(L))

把区间从中间分成两半，分别求最小值，再对两个结果取较小者。递归式为 $T(n)=2T(n/2)+1$ ，展开后仍是 $n-1$ 次比较；分治在这里没有减少比较次数，只是把“扫描”换成了“分解与合并”。切片会复制子列表，额外空间也更多。

三种写法解决的是同一个问题，差异在结构而不在结果。选择哪种写法要看后续是否需要并行、是否需要保留子问题的解，而不是看“分治”这个名字。

同时寻找最小值和最大值

分别调用两次“找最小值”需要约 $2n$ 次比较。把区间分成两半，让每个子问题同时返回最小值和最大值，可以在合并时把两个量一起处理，而不必分别扫描两遍。

1
A = [3, 8, 9, 4, 10, 5, 1, 17]
2

3

4
def Smin_max(a):
5
    if len(a) == 1:
6
        return (a[0], a[0])
7
    elif len(a) == 2:
8
        return (min(a), max(a))
9
    m = len(a) // 2
10
    lmin, lmax = Smin_max(a[:m])
11
    rmin, rmax = Smin_max(a[m:])
12
    return min(lmin, rmin), max(lmax, rmax)
13

14

15
print("Minimum and Maximum:%d,%d" % (Smin_max(A)))

基线有两种规模：一个元素时最小值和最大值都是它本身；两个元素时直接调用min和max得到两者。合并时左、右两半各自已经给出了一对值，只需再比较两个最小值、两个最大值各一次。

归并排序

归并排序先递归地把列表分成两半，分别排序，再用归并操作把两个有序列表合并。其中的merge定义在递归的归并操作中。

1
def msort(L):
2
    k = len(L)
3
    if k == 0:
4
        return L
5
    if k == 1:
6
        return L
7
    X1 = L[0 : k // 2]
8
    X2 = L[k // 2 : k]
9
    X1 = msort(X1)
10
    X2 = msort(X2)
11
    return merge(X1, X2)
12

13

14
print(msort([3, 1, 2]))

长度为0或1的列表已经有序，直接返回。对长度 $n>1$ 的列表，分解出两个规模约为 $n/2$ 的子列表，递归排序后合并。设合并的代价为 $O(n)$ ，则总时间为 $O(n\log n)$ ；归并需要 $O(n)$ 的辅助空间。

二进制加法

用True/False的列表表示二进制数，列表首元素是高位。全加器FA接收两个位和低位进位，输出本位和与向高位的进位。

1
def FA(a, b, c):  # Full adder
2
    carry = (a and b) or (b and c) or (a and c)
3
    sum = (
4
        (a and b and c)
5
        or (a and (not b) and (not c))
6
        or ((not a) and b and (not c))
7
        or ((not a) and (not b) and c)
8
    )
9
    return carry, sum

分治版先把两个数补成等长，再从中间切开。右半部分是低位，必须先算，因为它产生的进位要传给左半部分（高位）。

1
def add_divide(x, y, c=False):
2
    # x、y是True/False列表，c是低位进位
3
    # 返回向更高位的进位和x+y的结果列表
4
    while len(x) < len(y):
5
        x = [False] + x
6
    while len(y) < len(x):
7
        y = [False] + y
8
    if len(x) == 1:
9
        ctemp, stemp = FA(x[0], y[0], c)
10
        return (ctemp, [stemp])
11
    if len(x) == 0:
12
        return c, []
13
    c1, s1 = add_divide(x[len(x) // 2 : len(x)], y[len(y) // 2 : len(y)], c)
14
    c2, s2 = add_divide(x[0 : len(x) // 2], y[0 : len(y) // 2], c1)  # 依赖低位进位
15
    return (c2, s2 + s1)

计算过程可以分成三步：

补齐长度

在较短的数前面补False（高位补0），使两个列表等长。这样切分出的左右两半位数一致。
先算低位，再算高位

右半部分整体是低位，先递归计算，得到本位结果和向高位的进位；把该进位作为参数传给左半部分的递归调用。两个子问题的计算有先后依赖，不能交换顺序。
拼接结果

左半部分返回的进位是最终向更高位的进位；把左半部分的结果（高位）与右半部分的结果（低位）按顺序拼接，得到完整的结果列表。

例如add_divide([True, False, True], [True, True]) 计算 $5+3$ ，返回 (True, [False, False, False])：结果列表加上最高位的进位是1000，即十进制的8。

交互探索

对两段已排序的数据逐步执行合并，比较两段首元素并保持输出有序。

两段有序数据怎样合并？

逐步选择较小的首元素，合并两个有序序列。