分治算法
分治把问题拆成规模更小的同类问题,分别求解,再利用子问题结果构造原答案。要验证的不只是递归能结束,还包括:分解是否覆盖全部情况、合并是否遗漏跨边界关系、合并成本是否抵消了拆分收益。排序、计数和数值运算都可以用分治,不一定是求“最优解”。
例如订单记录按到达顺序携带递增序号,实际收到 [104, 101, 103, 102]。若较早到达的记录序号反而更大,就形成一个逆序对;这里共有 4 对。逆序对衡量相对于序号顺序的乱序程度,不等于丢失记录数,也不能单凭它定位网络故障。
分解后,跨边界的关系在哪里
将序列拆成连续的左、右两半。逆序对恰好分成三类:两项都在左边、都在右边、前项在左后项在右。前两类递归计算,第三类在归并两个已排序结果时计算。
左半 [104,101] 内有 1 对,排序后为 [101,104];右半 [103,102] 内有 1 对,排序后为 [102,103]。归并时先取 101,再取右边的 102、103,它们各自小于左边尚未取出的 104,增加 2 对,合计 4。
一般地,若右边当前值严格小于左边当前值,它也小于左边所有未取出的值,一次增加“左边剩余项数”。相等时先取左边,不计逆序,并维持相同值的相对顺序。这个合并规则是正确性的关键;只把两边计数相加,会漏掉所有跨边界逆序对。
完整实现:共享归并缓冲区
以下 Python 3 程序限定整数序号,拒绝布尔值;重复序号允许存在,相等不计逆序。输入只读取一次,不被修改,返回升序副本和逆序对数量。它只统计顺序关系,重复序号是否合法仍由业务合同决定。
python
def sort_and_count(sequence):
values = list(sequence)
if any(type(value) is not int for value in values):
raise ValueError("序号必须是整数")
buffer = [0] * len(values)
def solve(lo, hi):
if hi - lo <= 1:
return 0
mid = lo + (hi - lo) // 2
count = solve(lo, mid) + solve(mid, hi)
i, j, out = lo, mid, lo
while i < mid and j < hi:
if values[i] <= values[j]:
buffer[out] = values[i]
i += 1
else:
buffer[out] = values[j]
j += 1
count += mid - i
out += 1
while i < mid:
buffer[out] = values[i]
i += 1
out += 1
while j < hi:
buffer[out] = values[j]
j += 1
out += 1
for out in range(lo, hi):
values[out] = buffer[out]
return count
count = solve(0, len(values))
return values, count
arrivals = [104, 101, 103, 102]
assert sort_and_count(arrivals) == ([101, 102, 103, 104], 4)
assert arrivals == [104, 101, 103, 102]
assert sort_and_count([]) == ([], 0)
assert sort_and_count([2, 2, 1]) == ([1, 2, 2], 2)
print(sort_and_count(arrivals))所有区间使用 [lo, hi)。空区间和单元素区间直接返回 0,奇数长度也会被不重不漏地拆成 [lo, mid) 与 [mid, hi)。缓冲区每层只使用当前区间,左右递归顺序执行,因此可以复用一个长度 n 的数组。
按整数比较与加法近似常数计,时间为 O(n log n):每层合并总共处理 O(n) 项,层数为 O(log n)。输入副本、缓冲区合计 O(n) 空间,递归栈 O(log n)。共享缓冲区减少分配次数,但不是 O(1) 空间的原地排序。任意大整数的比较、计数也有位数成本。
递推关系与主定理的适用范围
对近似等分的递归,常写为 T(n)=aT(n/b)+f(n),其中 a≥1、b>1 为常数,f(n) 是递归以外的分解与合并成本。令 p=logᵦa,常用的三个情形为:
| f(n) 与 nᵖ 的关系 | 额外条件 | 结论 |
|---|---|---|
| f(n)=O(nᵖ⁻ᵋ),某个 ε>0 | 相差一个多项式因子 | T(n)=Θ(nᵖ) |
| f(n)=Θ(nᵖ) | 常用的等阶情形 | T(n)=Θ(nᵖ log n) |
| f(n)=Ω(nᵖ⁺ᵋ),某个 ε>0 | 还需正则条件:对充分大的 n,a·f(n/b)≤c·f(n),某个 c<1 | T(n)=Θ(f(n)) |
归并的递推是 2T(n/2)+Θ(n),因此为 Θ(n log n)。仅写 O(n) 作为合并上界,不足以单靠等式推出紧确 Θ 结论。取整通常只改变常数和边界,但要保证问题实际按此规模递减。
不等比例的子问题、变化的分支数、快速排序的最坏分割,都不能硬套这个形式。比如每次分为 0 与 n-1,递推为 T(n-1)+Θ(n),总成本是 Θ(n²)。此时用递归树、求和或代入法分析。
其他分治模型要保留什么信息
| 模型 | 子问题结果与合并 | 关键边界 |
|---|---|---|
| 归并排序 | 两个有序序列归并 | 稳定性取决于相等时先取哪侧;实现见排序算法 |
| 快速排序 | 分区后分别排序较小区间 | 三路分区必须定义等值区间是闭还是开,右递归不能跳过第一个大于基准的项 |
| 最大连续子数组 | 左内、右内、跨中点三种候选 | 空数组与是否允许空子数组需明确;全负数组不能无条件返回 0 |
| 最近点对 | 两侧最短距离,再检查跨分界带 | 按唯一点身份划分两侧,不能只按 x≤中点拆 y 序列而与 x 序列不一致 |
| Karatsuba 乘法 | 三次较小乘法恢复高低位交叉项 | 位数成本与符号单独处理;Python 内置大整数乘法不等于手写朴素乘法 |
| Strassen 矩阵乘法 | 七个块乘积组合四块结果 | 校验形状与可乘性;补零后裁回原尺寸,关注数值误差和实际阈值 |
| 快速幂 | 半指数结果复用一次,再平方 | 先定义非负整数指数或负指数合同;模运算版本见数学算法 |
二分查找每轮只继续一个子区间,通常也称减治;可按广义分治理解,但没有归并两个答案的过程。它的正确性依赖有序性和区间不变量,详见搜索算法。不要把“代码里有递归”当成分治的充分条件。
分治适合子问题能分别求解的情况;若不同分支反复计算相同状态,可以考虑记忆化与动态规划。跨边界信息不一定能从单个标量恢复,例如只返回两侧最大子数组和,不足以计算跨边界答案,必须额外扫描或返回前缀、后缀等摘要。
从教学递归到工程实现
日志合并、外部排序等场景常先生成可装入内存的有序块,再合并多个流。此时瓶颈可能是磁盘、网络与文件句柄,而非整数比较;中间文件生命周期、失败重试与稳定排序键都应纳入合同。不能把内存版递归的空间结论直接搬到外部处理。
子问题可独立求解,也不意味着并行一定更快。任务创建、数据复制和合并都有开销,共享缓冲区还需确保并行任务只写各自区间。小任务通常直接计算更合算;具体阈值须在真实运行时与输入分布下测量。
本例可用双重循环统计所有 i<j 且 a[i]>a[j] 作为小规模基准,比较计数和排序结果。应覆盖空序列、单项、重复值、已排序、逆序、奇数长度、负数与非法输入。性能测量应去掉逐层打印,分别观察耗时、峰值内存和分配量,不能用一次微秒计时宣称加速。
