6.1 分治法：大事化小的功法

6.1 分治法：大事化小的功法

本节摘要：分治法的三段式是分解、解决、合并——把规模 n 的问题切成 a 个规模 n/b 的同型子问题，递归解决后合并结果。复杂度由子问题个数 a、缩小比例 b、合并成本三要素决定，主定理给出三个量级档位。本节用归并思想数逆序对、用平方取幂演示"每轮减半"的威力，并划出分治的适用边界（子问题必须独立，否则请看下一节动态规划）。

把大象装进冰箱，一共几步

分治法的三步你早已见过两次：快速排序先分区（分解出两个独立子数组），各自递归（解决），无需合并；归并排序对半切（分解免费），递归到单元素（解决天然完成），双指针合并（合并是主戏）。抽象成模板：

• 分解：把问题切成若干规模更小的同型子问题；
• 解决：子问题足够小时直接求解（地基情形）；
• 合并：把子问题的答案拼成原问题的答案。

三步里藏着一个生死条件：子问题之间必须互相独立。切出来的两半各算各的、互不引用对方的中间结果，合并时只需要最终答案。一旦子问题重叠（比如朴素斐波那契的 fib(n-1) 与 fib(n-2) 都要算 fib(n-3)），分治就把同一份账翻来覆去地算——那是下一节动态规划的地盘。

复杂度账记成 T(n) = a·T(n/b) + f(n)：a 个子问题、每个规模缩到 n/b、合并花 f(n)。主定理用三个量级档位给答案，不需要背完整定理，记三个代表就够：

二分查找是 a=1、b=2、f=O(1) 的极简分治：一层只留一个子问题，每层只花常数——O(log n) 的另一副面孔。

分治的顺手收获：边归并边数逆序对

逆序对：i 小于 j 但 a[i] 大于 a[j] 的配对，是 5.1 节"乱度"的硬指标。暴力数要 O(n²)；归并排序的合并步骤里，每次从右段取元素时，左段剩余的所有元素都比它大——一次打包计数：

# 逆序对计数：分治三段式 + 暴力对拍
def count_inversions_dc(a):
    count = [0]
    def msort(seg):
        if len(seg) <= 1:
            return seg
        mid = len(seg) // 2
        left, right = msort(seg[:mid]), msort(seg[mid:])   # 分解 + 解决
        out, i, j = [], 0, 0
        while i < len(left) and j < len(right):            # 合并：顺便计数
            if left[i] <= right[j]:
                out.append(left[i]); i += 1
            else:
                count[0] += len(left) - i   # 右段胜出：左段剩余全体与它构成逆序对
                out.append(right[j]); j += 1
        out.extend(left[i:]); out.extend(right[j:])
        return out
    msort(list(a))
    return count[0]

def count_inversions_brute(a):            # O(n²) 对拍用
    c = 0
    for i in range(len(a)):
        for j in range(i + 1, len(a)):
            if a[i] > a[j]:
                c += 1
    return c

data = [5, 2, 4, 1, 3]
print("分治计数：", count_inversions_dc(data), "；暴力对拍：", count_inversions_brute(data))
# 输出：分治计数： 7 ；暴力对拍： 7
# 七对：5 压 2、4、1、3；2 压 1；4 压 1、3——逐对可验证
​

这正是"分治顺手做统计"的通用模式：合并时左右两段各自有序，跨段的统计量可以用段长直接结算，不必逐对枚举。归并求逆序对之外，平面最近点对、大整数乘法（Karatsuba）走的都是同一条路。

每轮减半的威力：快速幂

计算 x 的 n 次方，朴素做法连乘 n-1 次；分治的视角是 xⁿ 等于 x 的 n/2 次方的平方（n 偶数）或再乘一个 x（n 奇数）——每轮规模减半：

# 快速幂：递归减半 vs 朴素连乘，乘法次数计数
def naive_pow(x, n):
    r, mults = 1, 0
    for _ in range(n):
        r *= x
        mults += 1
    return r, mults

def fast_pow(x, n):
    mults = [0]
    def rec(x, n):
        if n == 0:
            return 1
        half = rec(x, n // 2)          # 只算一次半规模
        mults[0] += 1                  # 平方计一次
        r = half * half
        if n % 2 == 1:
            r *= x
            mults[0] += 1              # 补乘计一次
        return r
    return rec(x, n), mults[0]

v1, m1 = naive_pow(3, 100)
v2, m2 = fast_pow(3, 100)
print("结果一致：", v1 == v2)
print(f"朴素连乘 {m1} 次乘法；快速幂 {m2} 次乘法")
# 输出：
# 结果一致： True
# 朴素连乘 99 次乘法；快速幂 10 次乘法
# 指数每轮减半：乘法次数介于 log2(n) 与 2·log2(n) 之间，本例 10 次；
# 指数越大差距越悬殊——n 为一百万时，朴素百万次对快速幂约四十次
​

快速幂是密码学的地基之一（模幂运算），也是"减治法"（每轮只留一个子问题）的代表——与二分查找同一族。

⚠️ 常见坑：只看分解的层数不看合并的成本。切得再碎，合并若要 O(n²)，总量仍是 O(n²)。动笔前把三要素 a、b、f 都摆上桌，查档位表再下手。

💡 关键直觉：分治的本质优势是"对数深度的复用"——每层把问题规模按比例压，log 轮就到底。它不是让每层变快，而是让层数变成对数。

走火入魔：拿分治硬啃重叠子问题

典型事故：用分治写斐波那契。fib(30) 触发两百多万次调用（1.3 节已复现），因为 fib(28) 被两条递归链各算一遍——子问题不独立，分治的复杂度账 T(n) = 2T(n-1) + O(1) 直接爆炸成指数。判断口诀：画出前两层的递归调用树，若同一子问题出现两次以上，分治就该退场，记忆化或填表（下一节）登场。

本节要点回顾

• 三段式：分解、解决、合并；适用前提是子问题相互独立；
• 复杂度三要素 a、b、f 对应主定理三档位，记归并（n log n）、二分（log n）、根重（f(n)) 三个代表即可；
• 合并步骤可以顺手做统计：逆序对在归并时按段长批量结算，五元素七对可对拍复算；
• 快速幂展示减治（每轮一个子问题）的威力：一百次方十四次乘法对九十九次；
• 边界警示：递归树前两层出现重复子问题，说明该换动态规划。

子问题一旦重叠，账本就该登场。下一节：动态规划，用一张表终结重复计算。