Skip to content

约 3 分钟阅读

分治算法 ​

分治把问题拆成规模更小的同类问题,分别求解,再利用子问题结果构造原答案。要验证的不只是递归能结束,还包括:分解是否覆盖全部情况、合并是否遗漏跨边界关系、合并成本是否抵消了拆分收益。排序、计数和数值运算都可以用分治,不一定是求“最优解”。

例如订单记录按到达顺序携带递增序号,实际收到 [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<1T(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] 作为小规模基准,比较计数和排序结果。应覆盖空序列、单项、重复值、已排序、逆序、奇数长度、负数与非法输入。性能测量应去掉逐层打印,分别观察耗时、峰值内存和分配量,不能用一次微秒计时宣称加速。

别急,先让缓存热一下。