02 分治算法

本章对应考试中的：D1 逆序对计数（2011影印 等）、D2 股票买卖最大收益（样题1/试卷1/试卷3）、D3 网球循环赛日程表（样题2/试卷2）、D4 假币问题（试卷6，中英双语）、以及填空题第 4 题棋盘覆盖（试卷5）。
分治大题的作答格式很固定：写思路 → 写伪代码 → 用递推式算复杂度 → 与蛮力法比较。把这一套练熟，分治题就稳了。

核心考点

分治（divide and conquer）：把一个规模为 $n$ 的大问题，切成几个规模更小、类型相同、互不相干的子问题，分别解决后再把结果合并成原问题的答案。

这一章每道题都要求四样东西，缺一不可：

分治思路：怎么切、怎么合。
伪代码：写出递归函数（含递归出口）。
时间复杂度：写出递推式并解出来（解法见 01_数学基础_渐进记号与递推式求解.md）。
与蛮力法比较：说明分治比"硬算"快在哪。

从零开始的前置知识

什么是递归与递归出口

递归（recursion）：一个函数在自己内部又调用自己。分治算法几乎都用递归实现——解决大问题时，调用同一个函数去解决更小的子问题。

递归出口（base case）：规模小到不能再分时，直接给出答案、不再递归。没有出口的递归会无限调用下去。例如"规模为 1 时直接返回"。

一个最简单的递归例子，求 $1 + 2 + \dots + n$ ：

text

Sum(n):
    if n == 1: return 1        // 递归出口
    return n + Sum(n-1)        // 自己调用自己，规模减 1

分治的三步

任何分治算法都是这三步：

分（divide）：把规模 $n$ 的问题分成若干个规模更小的同类子问题（通常是二分，分成两个规模 $n / 2$ 的）。
治（conquer）：递归地解这些子问题；当规模小到出口时直接解。
合（combine）：把子问题的解合并成原问题的解。

标准例子：归并排序

归并排序（merge sort） 是分治的样板，后面 D1 逆序对就建立在它上面，务必先弄懂。它把 $n$ 个数排好序：

分：把数组从中间切成左右两半。
治：递归地把左半、右半各自排好序。
合：把两个已排好序的半段合并成一个有序的整段。

合并两个有序段的方法（关键）：两个段各放一个指针指向开头，比较两个指针所指元素，把较小的取出放进结果，对应指针后移；重复直到取完。

举例，合并左段 [2,5] 和右段 [1,3]：

比 2 与 1，取 1；比 2 与 3，取 2；比 5 与 3，取 3；右段空，取剩下的 5。结果 [1,2,3,5]。

复杂度：递推式 $T (n) = 2 T (n / 2) + O (n)$ （分成 2 个 $n / 2$ 子问题，合并需扫一遍 $O (n)$ ），用主定理解得 $T (n) = O (n \log n)$ （详见 01）。

答题模板

【分治思路】
  ① 分：把规模 n 的问题从中间分成两个规模约 n/2 的同类子问题；
  ② 治：递归求解左、右两个子问题（规模小到出口时直接解）；
  ③ 合：处理"跨越两半"的情况，把子问题结果合并为原问题的解。
【伪代码】写出递归函数 Solve(数据, left, right)，含 if left≥right 的出口。
【复杂度】写出递推式 T(n)=2T(n/2)+O(合并代价)，用主定理解出 O(...)。
【与蛮力比较】蛮力 O(n^2) 或更高，分治 O(n log n)，n 大时分治明显更优。

逐题精解

D1 逆序对计数（`2011影印` 等）

原题：给定互不相等的 $n$ 个数的序列 $a_{1}, \dots, a_{n}$ ，若 $a_{i} > a_{j}$ 且 $i < j$ ，则称 $a_{i}, a_{j}$ 是逆序的。写一个分治算法计算序列中逆序对的总数，推导时间复杂性并与蛮力法比较。

前置：什么是逆序对。 一对位置 $(i, j)$ ，左边的下标小（ $i < j$ ）但左边的值反而大（ $a_{i} > a_{j}$ ），就叫一个逆序对。例如序列 [2,4,1,3] 中： $(2, 1)$ （位置 1,3）、 $(4, 1)$ （位置 2,3）、 $(4, 3)$ （位置 2,4）共 3 个逆序对。

思路（基于归并排序）。 在归并排序"合并"两个有序半段的过程中顺便数逆序对。关键观察：合并时左段指针指向 $a [i]$ 、右段指针指向 $a [j]$ ，如果 $a [j] < a [i]$ ，由于左段从 $i$ 到 mid 都是已排序的（都 $\geq a [i] > a [j]$ ），所以左段中从 $i$ 到 mid 的每个元素都与 $a [j]$ 构成逆序，一次性累加 mid-i+1 个。

伪代码：

text

num ← 0                                  // 全局逆序对计数
MergeCount(a, left, mid, right):
    i ← left, j ← mid+1, 临时数组 t
    while i ≤ mid and j ≤ right:
        if a[j] < a[i]:
            num ← num + (mid - i + 1)    // 左段 i..mid 都比 a[j] 大
            把 a[j] 放入 t; j++
        else:
            把 a[i] 放入 t; i++
    把左/右段剩余元素搬入 t，再写回 a[left..right]

MergeSortCount(a, left, right):
    if left < right:
        mid ← (left + right) / 2
        MergeSortCount(a, left, mid)
        MergeSortCount(a, mid+1, right)
        MergeCount(a, left, mid, right)

演示（序列 [2,4,1,3]）：左半 [2,4]、右半 [1,3] 各自排序后合并：

$i$ 指 2、 $j$ 指 1： $1 < 2$ ，左段 [2,4] 从当前位置到末尾有 2 个数都比 1 大，num += 2（此时 num=2），取 1；
$i$ 指 2、 $j$ 指 3： $3 > 2$ ，取 2；
$i$ 指 4、 $j$ 指 3： $3 < 4$ ，左段剩 [4] 1 个比 3 大，num += 1（num=3），取 3；
取剩下的 4。

共数出 3 个逆序对，与手数结果一致。

复杂度： $T (n) = 2 T (n / 2) + O (n) = O (n \log n)$ 。蛮力法：两层循环检查每一对 $(i, j)$ ， $O (n^{2})$ 。 $n$ 较大时分治明显更优。

D2 股票买卖最大收益（`样题1`/`试卷1`/`试卷3`）

原题：连续 $n$ 天每天股价 $p (1), \dots, p (n)$ ，某天买入、之后某天卖出，求收益最大的买入日和卖出日。例： $n = 4$ ， $p = [4, 1, 1.5, 3]$ ，应返回"第 2 天买、第 4 天卖"（每股挣 2）。

思路（分治三情形）。 把 $1. . n$ 从中间分成左右两半。收益最大的"买卖对"必属于下面三种之一：

完全在左半：买和卖都在左半 → 递归求左半；
完全在右半：买和卖都在右半 → 递归求右半；
跨越中点：买在左半、卖在右半 → 此时最优是"买在左半的最低价、卖在右半的最高价"，扫一遍左右半即可 $O (n)$ 求出。

三种取收益最大的那个。

伪代码：

text

MaxProfit(p, left, right):
    if left == right: return (收益 0, 无买卖)          // 出口：只有一天
    mid ← (left + right) / 2
    (利润L) ← MaxProfit(p, left, mid)                  // 情形①
    (利润R) ← MaxProfit(p, mid+1, right)               // 情形②
    minL ← p[left..mid] 中的最低价及其日子
    maxR ← p[mid+1..right] 中的最高价及其日子
    利润C ← maxR - minL                                // 情形③：跨中点
    return 三者中利润最大的那个（含对应买卖日）

演示（ $p = [4, 1, 1.5, 3]$ ）：分成左半 [4,1]、右半 [1.5,3]。

左半最优：第 1 天买 4、第 2 天卖 1，亏，最优收益其实是 0 或负；
右半最优：第 3 天买 1.5、第 4 天卖 3，收益 1.5；
跨中点：左半最低价是 1（第 2 天），右半最高价是 3（第 4 天），收益 $3 - 1 = 2$ 。

三者取最大 → 收益 2，第 2 天买、第 4 天卖，与题面答案一致。

复杂度： $T (n) = 2 T (n / 2) + O (n) = O (n \log n)$ 。蛮力：枚举所有买卖日对 $(i, j)$ ， $O (n^{2})$ 。另外本题还有更快的一遍扫描法（边扫边记录"此前出现过的最低价"，用当前价减最低价更新最大收益），只要 $O (n)$ 。

D3 网球循环赛日程表（`样题2`/`试卷2`）

原题： $n = 2^{k}$ 名选手循环赛，要求：每人与其他 $n - 1$ 人各赛一次；每人每天只赛一次； $n - 1$ 天赛完。设计一张 $n$ 行、 $n - 1$ 列的表，第 $i$ 行第 $j$ 列填"第 $i$ 个选手第 $j$ 天遇到的对手"。

思路（二分递归 + 复制块）。 把 $n$ 名选手分成上半 ${1, \dots, n / 2}$ 和下半 ${n / 2 + 1, \dots, n}$ ：

前 $n / 2 - 1$ 天：上半内部先打一个 $n / 2$ 人的小循环赛（递归得到左上角块），下半内部也打一个小循环赛（左下角块）。
后 $n / 2$ 天：让上半每个人轮流与下半每个人比赛（上半与下半交叉对阵），这部分可由"把左上角块的编号加上 $n / 2$ 复制到右下角、把左下角块复制到右上角"并配合轮转填出。

伪代码：

text

Table(n, 起始编号 a):
    if n == 2: 让编号 a 与 a+1 这两人直接比赛（1 天）
    else:
        Table(n/2, a)            // 上半递归（左上角）
        Table(n/2, a + n/2)      // 下半递归（左下角）
        填右上角、右下角：上半与下半在后 n/2 天交叉对阵（按轮转配对）

$n = 4$ （4 人 3 天）的完整赛程表（行=选手，列=天，格内=对手）：

选手＼天	第 1 天	第 2 天	第 3 天
选手 1	2	3	4
选手 2	1	4	3
选手 3	4	1	2
选手 4	3	2	1

验证：每行恰好出现其余 3 个人各一次（选手 1 遇到 2、3、4）；每列每人只赛一次（第 2 天的对阵是 1-3、2-4，无人重复）。第 1 天是上半 1-2、下半 3-4（小循环赛）；第 2、3 天是上半与下半交叉。

$n = 8$ （8 人 7 天）的完整赛程表（前 3 天是两个 4 人小循环赛，后 4 天上半 1-4 与下半 5-8 交叉）：

选手＼天	1	2	3	4	5	6	7
1	2	3	4	5	6	7	8
2	1	4	3	6	7	8	5
3	4	1	2	7	8	5	6
4	3	2	1	8	5	6	7
5	6	7	8	1	4	3	2
6	5	8	7	2	1	4	3
7	8	5	6	3	2	1	4
8	7	6	5	4	3	2	1

可以看到左上角 4×3 块就是上面 $n = 4$ 的表，左下角是它"编号加 4"的复制；右半四天是上半与下半的交叉对阵。这正体现了"复制块"的分治结构。

复杂度： $T (n) = 2 T (n / 2) + O (n^{2} / 2) = O (n^{2})$ （填表与复制块的工作量为 $O (n^{2})$ ，由主定理情况 3 得 $O (n^{2})$ ）。蛮力：逐天逐人枚举可行对手，约 $O (n^{3})$ 。

D4 假币问题（`试卷6`，中英双语，15 分）

原题： $N$ 枚外形相同的硬币中有一枚是假币（比真币轻），用一架没有砝码的天平，描述一个找出假币的算法并分析运行时间。

思路（三分法）。 每次把硬币尽量平均分成三堆 $A, B, C$ ，使 $| A | = | B |$ 。把 $A$ 放天平左盘、 $B$ 放右盘称量：

若不平衡：假币在较轻的那一堆里；
若平衡： $A, B$ 都是真币，假币在没上称的 $C$ 堆里。

每称一次就把搜索范围缩到约原来的 $1 / 3$ ，对那一堆递归。

伪代码：

text

FindFake(coins):
    if 只剩 1 枚: return 它
    把 coins 尽量三等分为 A, B, C（|A|=|B|）
    称量 A 与 B:
        若 A 轻: return FindFake(A)
        若 B 轻: return FindFake(B)
        若平衡:  return FindFake(C)

演示（9 枚硬币）：分成 3 堆各 3 枚，称第一堆与第二堆。若平衡 → 假币在第三堆；再从第三堆取 2 枚各放一盘称量，轻的那枚就是假币，若平衡则剩下没称的那枚是假币。共 2 次称量（ $\log_{3} 9 = 2$ ）。

复杂度： $T (N) = T (N / 3) + O (1) = O (\log_{3} N)$ 次称量。

棋盘覆盖（填空题第 4 题，`试卷5`）

原题：用分治策略覆盖 $2^{k} \times 2^{k}$ 的特殊棋盘（棋盘上有一个"特殊方格"不需覆盖），用 L 型骨牌覆盖其余所有方格。问：所需 L 型骨牌个数 = （　）；时间复杂性 $T (k) =$ （　）。

前置：什么是 L 型骨牌。 L 型骨牌（L-tromino） 是由 3 个相连方格组成的"L"形块，每块正好盖住 3 个方格。

思路（分四块）。 把 $2^{k} \times 2^{k}$ 棋盘从中间分成 4 个 $2^{k - 1} \times 2^{k - 1}$ 的子棋盘。特殊方格只落在其中 1 个子棋盘里。在棋盘正中央放一个 L 型骨牌，盖住"另外 3 个没有特殊方格的子棋盘"各自挨着中心的那个角——这样这 3 个子棋盘也各自有了一个"被盖住的格子"，相当于各自有了一个"特殊方格"。于是 4 个子棋盘都变成了同类的小问题，递归处理。

两个填空的答案：

L 型骨牌个数 $= \frac{4^{k} - 1}{3}$ 。推导：棋盘共 $2^{k} \times 2^{k} = 4^{k}$ 个方格，去掉 1 个特殊方格还剩 $4^{k} - 1$ 个要盖；每块 L 型骨牌盖 3 个，故 $\frac{4^{k} - 1}{3}$ 块（ $4^{k} - 1$ 恰能被 3 整除）。
时间复杂性 $T (k) = 4 T (k - 1) + O (1) = O (4^{k})$ 。每次把问题分成 4 个规模 $k - 1$ 的子问题、外加放 1 块骨牌的常数工作 $O (1)$ 。解这个递推（详见 01）得 $O (4^{k})$ ，与骨牌总数同阶。

高频陷阱 / 易错点小结

递归一定要写出口（if left==right/if n==1），否则无限递归。
复杂度靠递推式：分治题的复杂度结论统一来自 $T (n) = 2 T (n / 2) + O (合并)$ ，别凭感觉写。
逆序对累加的是 mid-i+1（左段当前到末尾的个数），不是 1，这是该题最易错处。
股票题的跨中点情形是"左半最低买、右半最高卖"，不要写成左右各自最优。
每题都要写"与蛮力法比较"，这是固定采分点。
网球赛复杂度是 $O (n^{2})$ 不是 $O (n \log n)$ ，因为合并（复制块）代价是 $O (n^{2})$ 而非 $O (n)$ 。

自测清单

[ ] 说清分治三步（分/治/合），并完整描述归并排序的合并过程。
[ ] 写出逆序对算法，并对 [2,4,1,3] 数出 3 个逆序对。
[ ] 写出股票买卖的分治三情形，对 $p = [4, 1, 1.5, 3]$ 得"2 买 4 卖、收益 2"。
[ ] 默写 $n = 4$ 的网球赛 3 列赛程表，并说出复杂度 $O (n^{2})$ 。
[ ] 说出假币三分法的复杂度 $O (\log_{3} N)$ 。
[ ] 写出棋盘覆盖的骨牌数 $(4^{k} - 1) / 3$ 和 $T (k) = O (4^{k})$ 。

02 分治算法 ​

核心考点 ​

从零开始的前置知识 ​

什么是递归与递归出口 ​

分治的三步 ​

标准例子：归并排序 ​

答题模板 ​

逐题精解 ​

D1 逆序对计数（2011影印 等） ​

D2 股票买卖最大收益（样题1/试卷1/试卷3） ​

D3 网球循环赛日程表（样题2/试卷2） ​

D4 假币问题（试卷6，中英双语，15 分） ​

棋盘覆盖（填空题第 4 题，试卷5） ​

高频陷阱 / 易错点小结 ​

自测清单 ​

02 分治算法

核心考点

从零开始的前置知识

什么是递归与递归出口

分治的三步

标准例子：归并排序

答题模板

逐题精解

D1 逆序对计数（`2011影印` 等）

D2 股票买卖最大收益（`样题1`/`试卷1`/`试卷3`）

D3 网球循环赛日程表（`样题2`/`试卷2`）

D4 假币问题（`试卷6`，中英双语，15 分）

棋盘覆盖（填空题第 4 题，`试卷5`）

高频陷阱 / 易错点小结

自测清单