2.4　分治：切开、解决、合并

学习目标：学完本节，你能

• 说出分治三步，并判断一个问题适不适合用分治；
• 写出分治算法，并用「每层工作量 × 层数」估算它的复杂度；
• 区分分治与减治，知道「把规模砍半」为什么威力巨大。

先修：2.1–2.3（递归的写法、代价与改写）。 固定术语：分治、减治。 环境与版本：.NET 8 / C# 12。 预计阅读：28 分钟。

一、直觉：数硬币

桌上有一大堆硬币，要数清楚有多少枚。

• 一个人数：一枚一枚点，1000 枚就要点 1000 次。
• 四个人数：每人分一堆各数各的，最后把四个数加起来。理论上快 4 倍。

但分工不是没有代价的：

1. 分堆要时间 —— 你得先把硬币分成四份。
2. 汇总要时间 —— 四个人报数，你还要相加。
3. 如果只有 4 枚硬币，分堆和汇总的时间比直接数还长。

这就是分治的全部内容：把大问题切成小问题，分别解决，再合并结果。 收益来自"小问题更容易处理"（在有多个处理单元时还能并行），成本来自切分与合并。

二、形式化：分治三步

分治能成立，需要三个前提：

1. 子问题和原问题同类型。 否则没法用同一个递归函数处理。（数硬币的子问题还是"数硬币"。）
2. 子问题互相独立。 如果子问题之间有重叠，你就会重复计算 —— 那时候该用的是动态规划（第 15 章）。
3. 合并要可行，而且不能太贵。 如果合并的代价比省下来的还多，分治就是亏的（下面例 1 会看到）。

分治 vs 减治

两者都靠"把规模砍半"提速，但分治要处理两边，减治只需要处理一边。

一个容易混淆的点：二分查找虽然叫"分"，但它每次只往一边走，所以它是减治，不是分治。这个区分在第 8 章会变得很重要 —— 归并排序是分治（$O(n \log n)$），而快速幂式的减治能达到 $O(\log n)$。

三、例题 1：分治求最大值（分治不等于更快）

新建控制台项目，粘贴代码：

using System.Diagnostics;

const long MOD = 1_000_000_007;

// ==================== 例 1：分治求最大值 ====================
//
// 分治三步：切开（分成左右两半）-> 解决（各自递归求最大值）-> 合并（取两者较大值）

static int MaxDivideConquer(int[] a, int lo, int hi)
{
    if (lo == hi) return a[lo];                          // 基准情形：只剩一个元素

    int mid = (lo + hi) / 2;
    int leftMax = MaxDivideConquer(a, lo, mid);          // 切开 + 解决左半
    int rightMax = MaxDivideConquer(a, mid + 1, hi);     // 切开 + 解决右半
    return Math.Max(leftMax, rightMax);                  // 合并
}

static int MaxLinear(int[] a)
{
    int best = a[0];
    for (int i = 1; i < a.Length; i++)
        if (a[i] > best) best = a[i];
    return best;
}

// ==================== 例 2：快速幂 ====================
//
// 朴素做法：b 连乘 e 次，O(e)
// 分治做法：b^e = (b^(e/2))^2，每次把指数砍一半，O(log e)

long naiveMultiplications = 0;
long fastMultiplications = 0;

static long PowerNaive(long b, int e, ref long counter)
{
    long result = 1;
    for (int i = 0; i < e; i++)
    {
        result = result * b % MOD;
        counter++;
    }
    return result;
}

static long PowerFast(long b, int e, ref long counter)
{
    if (e == 0) return 1;

    long half = PowerFast(b, e / 2, ref counter);
    counter++;                                   // half * half 这一次乘法
    long result = half * half % MOD;

    if (e % 2 == 1)
    {
        result = result * b % MOD;
        counter++;                               // 奇数时还要多乘一次 b
    }
    return result;
}

// ==================== 例 3：分治求和的代价 ====================

// 注意返回类型用 long：10 万个百万以内的数相加约 5×10^10，超出 int 上限会静默溢出
static long SumDivideConquer(int[] a, int lo, int hi)
{
    if (lo == hi) return a[lo];
    int mid = (lo + hi) / 2;
    return SumDivideConquer(a, lo, mid) + SumDivideConquer(a, mid + 1, hi);
}

static long SumLinear(int[] a)
{
    long s = 0;
    foreach (var x in a) s += x;
    return s;
}

// ==================== 主流程 ====================

var rng = new Random(42);
int[] data = new int[100_000];
for (int i = 0; i < data.Length; i++) data[i] = rng.Next(0, 1_000_000);

Console.WriteLine("=== 例 1：找最大值，分治 vs 线性扫描 ===");
int maxDC = MaxDivideConquer(data, 0, data.Length - 1);
int maxLinear = MaxLinear(data);
Console.WriteLine($"  分治结果   : {maxDC}");
Console.WriteLine($"  线性结果   : {maxLinear}   一致={maxDC == maxLinear}");
Console.WriteLine($"  数据规模   : {data.Length:N0}");
Console.WriteLine($"  两者比较次数都是约 n 次 —— 分治在这里没有优势，只是多了一层调用开销。");
Console.WriteLine();

Console.WriteLine("=== 例 2：快速幂的乘法次数对比（结果对 1,000,000,007 取模）===");
Console.WriteLine($"{"指数 e",10} | {"朴素乘法次数",14} | {"分治乘法次数",14} | {"倍数",8}");
foreach (int e in new[] { 100, 1_000, 10_000, 100_000 })
{
    naiveMultiplications = 0;
    fastMultiplications = 0;

    long r1 = PowerNaive(2, e, ref naiveMultiplications);
    long r2 = PowerFast(2, e, ref fastMultiplications);

    Console.WriteLine($"{e,10:N0} | {naiveMultiplications,14:N0} | {fastMultiplications,14:N0} | " +
                      $"{(double)naiveMultiplications / fastMultiplications,8:F1}  一致={r1 == r2}");
}
Console.WriteLine();

Console.WriteLine("=== 例 3：求和，分治 vs 线性（分治不一定更快）===");

var sw = Stopwatch.StartNew();
long s1 = SumDivideConquer(data, 0, data.Length - 1);
sw.Stop();
double dcMs = sw.Elapsed.TotalMilliseconds;

sw.Restart();
long s2 = SumLinear(data);
sw.Stop();
double linearMs = sw.Elapsed.TotalMilliseconds;

Console.WriteLine($"  分治求和: {dcMs,8:F3} ms   结果 = {s1:N0}");
Console.WriteLine($"  线性求和: {linearMs,8:F3} ms   结果 = {s2:N0}");
Console.WriteLine($"  线性快 {dcMs / linearMs:F1} 倍 —— 分治的递归调用是有成本的。");

实测输出（.NET 8 Release）：

=== 例 1：找最大值，分治 vs 线性扫描 ===
  分治结果   : 999991
  线性结果   : 999991   一致=True
  数据规模   : 100,000
  两者比较次数都是约 n 次 —— 分治在这里没有优势，只是多了一层调用开销。

=== 例 2：快速幂的乘法次数对比（结果对 1,000,000,007 取模）===
      指数 e |         朴素乘法次数 |         分治乘法次数 |       倍数
       100 |            100 |             10 |     10.0  一致=True
     1,000 |          1,000 |             16 |     62.5  一致=True
    10,000 |         10,000 |             19 |    526.3  一致=True
   100,000 |        100,000 |             23 |   4347.8  一致=True

=== 例 3：求和，分治 vs 线性（分治不一定更快）===
  分治求和:    0.309 ms   结果 = 49,992,014,743
  线性求和:    0.250 ms   结果 = 49,992,014,743
  线性快 1.2 倍 —— 分治的递归调用是有成本的。

四、读懂例 1：为什么分治在这里没用

分治找最大值，比较次数并不会比线性扫描少。

原因很直接：不管怎么切，每个元素都必须被看一次。 分成两半只是把"看一遍"这件事分散到树的不同节点上，总数一点没变。分治带来的只是额外的递归调用开销。

用递推式写出来就清楚了。设规模 $n$ 需要的时间是 $T(n)$：

$$T(n) = \underbrace{2T(n/2)}{\text{解决左右两半}} + \underbrace{O(1)}{\text{合并（取最大值）}}$$

用"每层工作量 × 层数"来算：

总工作量 = 各层之和：

$$1 + 2 + 4 + \cdots + n \approx 2n = O(n)$$

和线性扫描一样是 $O(n)$。 分治用更复杂的结构，换来了同样的复杂度 —— 这笔交易是亏的。

这个"每层工作量"的分析方法比主定理更好用，也更直观。 记住它： 总复杂度 = 每层的工作量 × 层数。

五、例 2：把指数砍半的威力

现在看一个分治/减治真正大显身手的地方 —— 计算 $b^e \bmod m$（在密码学、哈希、随机数生成里到处都有）。

朴素做法：连乘 $e$ 次，$O(e)$。$e = 100{,}000$ 时要做 10 万次乘法。

砍半做法：利用这个恒等式

$$b^e = \begin{cases} (b^{e/2})^2 & e \text{ 是偶数} \[4pt] (b^{(e-1)/2})^2 \cdot b & e \text{ 是奇数} \end{cases}$$

每次递归把指数砍一半，所以只需要 $\log_2 e$ 层。

实测数据（乘法次数）：

注意这个规律：$e$ 涨 10 倍，砍半做法只多 3～6 次乘法。

因为 $\log_2(100000) \approx 16.6$，而 $\log_2(10000) \approx 13.3$ —— $e$ 翻十倍，指数才涨 3.3。

这意味着什么？

$e = 10^{18}$ 时，朴素做法需要 100 亿亿次乘法，砍半做法只需要 60 次。 这就是"改变增长方式"相较于"优化常数"的压倒性优势 —— 1.2 节讲的道理，在这里有了一个极端而真实的例证。

RSA 加密能在一瞬间完成，靠的就是这个算法。 如果 RSA 用的是朴素幂运算，用 2048 位的密钥加密一个字节都需要比宇宙年龄更长的时间。

六、例 3：分治的代价是真的

例 3 对比了分治求和与线性求和：

  分治求和:    0.309 ms   结果 = 49,992,014,743
  线性求和:    0.250 ms   结果 = 49,992,014,743
  线性快 1.2 倍

分治慢了 1.2 倍。 注意这里的差距不大，是因为求和本身太简单了（一次加法），递归的函数调用开销占了主要部分。

但这次对比说明了一件重要的事：分治不是免费的。每切一刀、每递归一层，都要付出：

• 函数调用开销（保存现场、传递参数、返回）
• 栈空间（2.2 节算过这笔账）
• 合并的开销（这里很便宜，归并排序里就很贵）

所以分治只在一种情况下划算：切开之后，子问题能被"更高效地"解决，从而省下远超切分成本的计算量。

• 归并排序省下了什么？它让"排序"从 $O(n^2)$ 变成 $O(n \log n)$ —— 省的是量级，所以值得。
• 找最大值省下了什么？什么都没省 —— 所以不值得。

判断口诀：问自己"分治之后，每层的总工作量是多少"。

• 找最大值：最后一层是 $O(n)$，总共 $O(n)$ —— 和线性一样，白切。
• 归并排序：每一层的合并总量都是 $O(n)$，一共 $\log n$ 层 —— 总共 $O(n \log n)$。这才是分治该有的样子：每层都干满活，层数才是 $\log n$。

下一章预告：归并排序的递推式是 $T(n) = 2T(n/2) + O(n)$。用"每层工作量 × 层数"算：每层 $O(n)$，共 $\log n$ 层，所以是 $O(n \log n)$。8.1 节会把这个推导完整走一遍。

七、什么时候该用分治

一句话总结：分治的价值不在"分"，而在"分完之后每层还能干满活，且层数只有 $\log n$"。

八、练习

练习 2.4.1（算复杂度） 用"每层工作量 × 层数"的方法，估算下面两个递推式的复杂度： (a) $T(n) = 2T(n/2) + O(n)$ (b) $T(n) = 2T(n/2) + O(n^2)$

练习 2.4.2（判断） 下面四个问题，哪些适合用分治？说明理由。 (a) 在一个有序数组中查找某个值 (b) 统计一个数组中所有元素的和 (c) 把两个各自有序的数组归并成一个有序数组 (d) 计算 $n$ 个数的所有子集

练习 2.4.3（写代码） 用分治写一个函数，统计一个整数数组中有多少个偶数。先写出递归版本，再回答：这个分治有意义吗？ 为什么？

练习 2.4.4（挑战·推导） 考虑这个递推式：$T(n) = 2T(n/2) + O(\log n)$。 每层的工作量是 $\log n$、$\log n - 1$、$\log n - 2$……吗？请仔细想一想：在递归树的第 $k$ 层，子问题的规模是多少？那一层的合并工作量又是多少？ 算出总复杂度。

练习 2.4.5（挑战·工程） 你的团队要处理一个 1000 万行的日志文件，需要统计其中出现次数最多的 10 个 IP 地址。单机内存放不下整个文件（只有 2 GB）。 (a) 用分治思想设计一个方案。 (b) 说明这个方案为什么能成立，以及它的瓶颈在哪里。

九、练习答案

2.4.1

(a) $T(n) = 2T(n/2) + O(n)$

层数：$n$ 每次减半，到规模 1 需要 $\log_2 n$ 层。

总复杂度 $= n \times \log_2 n = O(n \log n)$。

这就是归并排序的复杂度。 关键点是：每一层的工作量都是 $n$，不随层数减少。

(b) $T(n) = 2T(n/2) + O(n^2)$

这一层的工作量在递减（每层减半），所以总和由第一层主导：

$$n^2 + \frac{n^2}{2} + \frac{n^2}{4} + \cdots < 2n^2 = O(n^2)$$

总复杂度是 $O(n^2)$。

这是分治的"坏情况"：根节点的合并太贵，把整棵树的成本都压在了顶部。分治在这里没有带来任何好处 —— 这种情况下就是"白切"。

2.4.2

• (a) 不适合分治，适合减治。 二分查找每次只往一边走（减治），复杂度 $O(\log n)$。如果硬要写成"两边都递归"，反而会变成 $O(n)$ —— 这是很常见的误区。
• (b) 不适合。 每个元素都必须看一遍，分治的合并（加法）只是把开销加上去。实测见例 3：分治慢了 1.2 倍。
• (c) 适合，这就是归并排序的合并步骤。 但这个操作本身是线性的（$O(m+n)$），不需要递归 —— 它是分治里"合并"那一环。归并排序是"分治"的典型，而"归并"本身不是。
• (d) 不适合。 $n$ 个数的子集有 $2^n$ 个，答案本身就比输入大得多，任何算法都逃不掉 $O(2^n)$。这属于回溯/枚举，不是分治。

2.4.3

static int CountEven(int[] a, int lo, int hi)
{
    if (lo == hi) return a[lo] % 2 == 0 ? 1 : 0;      // 基准情形：一个元素

    int mid = (lo + hi) / 2;
    int leftCount = CountEven(a, lo, mid);            // 左半
    int rightCount = CountEven(a, mid + 1, hi);       // 右半
    return leftCount + rightCount;                    // 合并：相加
}

这个分治没有意义。 理由和例 1 完全一样：

• 每个元素都必须被检查一次，没有任何子问题可以被跳过。
• 递归式为 $T(n) = 2T(n/2) + O(1)$，总复杂度 $O(n)$ —— 和一次简单循环一样。
• 但分治版本多了 $\log n$ 层的递归调用开销、占用了栈空间、代码也变长了。

改成循环：

static int CountEvenIterative(int[] a)
{
    int count = 0;
    foreach (var x in a)
        if (x % 2 == 0) count++;
    return count;
}

判断标准：分治能让某些子问题不被计算吗？ 不能，就别分治。 归并排序能赢，是因为它把"排序"这个大问题拆成了"排两半再合并"，从而让每层的合并变成线性的 $O(n)$ —— 它省下的是排序本身的复杂度，不是"少看了几个元素"。

2.4.4

容易犯的错误：以为"第 0 层工作量是 $\log n$，第 1 层是 $\log n - 1$……"。

正确的分析：$O(\log n)$ 这个合并代价，指的是在当前子问题规模下的合并代价。

在第 $k$ 层，子问题的规模是 $n/2^k$，所以每个子问题的合并代价是 $O(\log(n/2^k))$。

而第 $k$ 层有 $2^k$ 个子问题，所以该层的总工作量是：

$$2^k \times \log\frac{n}{2^k} = 2^k \left(\log n - k\right)$$

这个值随 $k$ 先增后减（因为 $2^k$ 在指数增长，而 $(\log n - k)$ 在递减），最大值出现在 $k$ 接近 $\log n$ 附近，量级为 $O(n)$。

求和：

$$T(n) = \sum_{k=0}^{\log n} 2^k (\log n - k) = O(n)$$

结论：$T(n) = O(n)$。

这个练习的要点：分析分治复杂度时，必须按"层"来算，而不是想当然地认为"合并代价就是 $\log n$"。第 $k$ 层有 $2^k$ 个子问题，每个都要付一次合并代价 —— 乘起来才是这一层的总开销。

顺带一提，"每层总工作量先增后减、最后求和"这类情况，标准做法是用递归树把每层的和写出来再加总。15 章之前的复杂度分析基本都能用这个方法搞定。

2.4.5

(a) 方案：两次分治

第一轮：分块统计

1. 把 1000 万行日志按顺序切成 $K$ 组（比如每组 100 万行，共 10 组）。
2. 每次只读一组进内存（100 万行约占几百 MB，2 GB 内存放得下）。
3. 对这一组，用一个哈希表统计每个 IP 出现的次数。
4. 统计完后，把哈希表按相同规则写回磁盘 —— 比如分成 256 个文件，按 IP 哈希值决定写入哪个文件。

关键点：同一个 IP 一定会被分到同一个文件里（因为哈希是确定的）。

第二轮：分别统计

1. 对 256 个文件中的每一个，单独读进内存（每个文件约占总量的 1/256，肯定放得下）。
2. 用哈希表统计这个文件里的 IP 频次。
3. 用小顶堆（第 11 章）取出这个文件的 Top 10。
4. 把 256 个文件的 Top 10 汇总（总共 2560 个候选），再取全局 Top 10。

(b) 为什么成立

• 内存可控：任何时候内存里最多只有一个分片的数据，而不是整个文件。
• 正确性有保证：同一个 IP 的所有记录必然落在同一个文件里，所以第二轮的局部统计不会漏掉任何一个 IP 的总数。
• 瓶颈在哪：
  1. 磁盘 I/O：数据要被完整读写两遍（一轮写出、二轮读入）。这在 SSD 上还好，机械硬盘上就是主要成本。
  2. 数据倾斜：如果某个 IP 的日志特别多（比如被 DDoS），256 个文件里会有一个特别大，可能还是放不进内存。这时需要在第一轮做二次拆分（对超大的分片再用不同的哈希函数拆一次）。
  3. 总耗时：两轮 I/O 无法避免，除非能一次性放进内存。

这就是 MapReduce 的核心思想：Map 阶段分片统计，Shuffle 阶段按 key 重分布，Reduce 阶段合并结果。你刚刚独立设计出的方案，和工业界的分布式计算框架是同一个思路 —— 而且它的本质就是分治：切开（分片）、解决（各自统计）、合并（汇总结果）。

十、常见错误

十一、本节总结

1. 分治三步：切开（Divide）→ 解决（Conquer）→ 合并（Combine）。
2. 分治成立的前提：子问题同类型、互相独立、合并可行。
3. 分治 vs 减治：分治每次处理全部子问题（$T(n) = 2T(n/2) + \ldots$），减治只处理一个（$T(n) = T(n/2) + \ldots$）。二分查找和快速幂都是减治。
4. 分析分治复杂度的通用方法：总复杂度 = 每层的工作量 × 层数。
   • $T(n) = 2T(n/2) + O(1)$ → 每层递减 → $O(n)$（找最大值，白切）
   • $T(n) = 2T(n/2) + O(n)$ → 每层都是 $n$ → $O(n \log n)$（归并排序，分治的典范）
   • $T(n) = 2T(n/2) + O(n^2)$ → 根部主导 → $O(n^2)$（白切）
5. 砍半的威力：$e$ 从 $10^4$ 涨到 $10^5$（10 倍），快速幂的乘法次数只从 19 次涨到 23 次。这是"改变增长方式"最直观的例子。
6. 判断该不该分治：问"分治能让某些子问题不被计算吗？每层还干满活吗？" 不能，就别分。

本章小结：第 2 章给了你递归这把"通用语言"。现在你应该能做到三件事 ——

• 写对递归：先找基准情形，再确认规模在缩小（2.1）；
• 看懂代价：递归空间 = 深度，栈溢出会杀掉整个进程（2.2）；
• 必要时改写：按三类改法把递归换成循环或显式栈（2.3）；
• 用对模式：知道什么时候该"一刀切两半"，什么时候那是白费力气（2.4）。

下一章衔接：从第 3 章开始，我们正式进入数据结构。第一站是最基础、也是最快的那一个 —— 数组。你将理解为什么"按下标访问是 $O(1)$"这句话背后有硬件层面的原因，为什么 List<T> 敢承诺"追加元素是 $O(1)$"，以及如何用双指针和滑动窗口把 $O(n^2)$ 的暴力解法降到 $O(n)$。

状态外显

{
  "book": "数据结构与算法自学：从工程直觉到复杂度思维",
  "section": "2.4",
  "title": "分治：切开、解决、合并",
  "covered": [
    "分治三步范式与三个成立前提",
    "分治 vs 减治的区别（二分查找与快速幂属于减治）",
    "分治找最大值的递推分析（每层递减 -> O(n)，白切）",
    "「每层工作量 × 层数」这一通用复杂度分析法",
    "快速幂的乘法次数实测（e 涨 10 倍只多 3-6 次乘法）",
    "T(n)=2T(n/2)+O(n) -> O(n log n) 的逐层推演",
    "分治求和的实测开销（比线性慢 1.2 倍）",
    "海量日志 Top-K 的分治方案（引出 MapReduce 思想）"
  ],
  "unresolved": [
    "归并排序的完整实现留到 8.1",
    "小顶堆求 Top-K 留到 11.4",
    "子问题重叠时改用动态规划留到第 15 章"
  ],
  "canonical_terms": {
    "分治": "切开、解决、合并三步范式，每次递归处理全部子问题",
    "减治": "每次递归只处理一个子问题，复杂度形态为 T(n)=T(n/2)+..."
  },
  "symbols_units": {},
  "assumptions": [
    "读者已掌握 2.1-2.3 的递归写法与代价",
    "读者能读懂简单的递推式（T(n) = 2T(n/2) + O(n)）"
  ],
  "word_count_actual": 2380,
  "checks": [
    "C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑，输出见正文",
    "项目文件：99-tools/samples/Ch02/Sec24/",
    "实测数据逐项核对：乘法次数 10/16/19/23，分治 0.309ms vs 线性 0.250ms",
    "快速幂乘法次数 23 已手工验算（17 次非零调用 + 6 个奇数指数 = 23）",
    "练习答案含关键步骤，不只给结果",
    "术语写法与 glossary.md 一致"
  ],
  "known_issues": [
    "初稿求和用 int 返回导致静默溢出（显示 -1547592809），已改为 long 并重测"
  ],
  "next": "3.1 连续内存：数组的红利与代价"
}