01 分治法基础：递归树与主定理——分治的思维骨架

分治法基础：递归树与主定理——分治的思维骨架

摘要

分治法（Divide and Conquer）是算法设计中最重要的范式之一，它将大问题拆分为若干个独立的小问题，递归求解后再合并结果。本文不仅介绍分治的三要素和经典例子，更重点讲解两个支撑性工具：递归树分析（直观推导分治复杂度的图形方法）和主定理（三种情形各自背后的数学逻辑）。理解这两个工具，你才能在面试中自信地分析任何分治算法的时间复杂度，而不是死记公式。

---

第 1 章 分治法的本质：为什么拆分能降低复杂度

1.1 从一个反例说起

假设你要在一个无序数组中查找某个元素。如果什么都不利用，暴力扫描需要 $O(n)$ 时间——这已经是这个问题的下界，没法优化。

但如果数组是有序的，你就可以利用有序性：取中间元素，如果比目标大就去左半段找，否则去右半段找。每次可以把搜索范围缩小一半，最终只需 $O(\log n)$ 次比较。

这就是二分查找——分治思想最直观的体现。它之所以快，不是因为”分割”本身节省了时间，而是因为分割之后，子问题的规模缩小了，而且每个子问题都比原问题简单。

这引出了分治法的核心直觉：当一个规模为 $n$ 的问题，可以分解为若干个规模为 $n/b$ 的独立子问题，且合并代价可控时，整体复杂度往往显著低于暴力方法。

1.2 分治的三要素

任何分治算法都可以分解为三个阶段：

第一阶段：分解（Divide）

将原问题分解为若干个规模更小的子问题。分解本身应该是”便宜”的——最好是 $O(1)$ 或 $O(n)$ 的，而不是比求解子问题还贵。

第二阶段：征服（Conquer）

递归地求解每个子问题。当子问题规模小到某个阈值（通常是规模为 1 或 2 的基础情形）时，直接求解，不再递归。

第三阶段：合并（Combine）

将各子问题的解合并为原问题的解。合并代价的大小直接决定了整体算法的复杂度。

核心概念：分治的正确性基础

分治法的正确性依赖于一个前提：子问题之间相互独立，没有重叠。如果子问题之间有大量重叠（同一个子问题被多次求解），就不应该用纯分治，而应该用动态规划（通过 memoization 避免重复计算）。这是区分”分治”与”动态规划”的核心分水岭，后续第 06 篇贪心算法中会进一步讨论这个三角关系。

1.3 用递推关系描述分治算法

分治算法的时间复杂度通常可以用以下递推关系描述：

$T(n)=a\cdot T\left(\frac{n}{b}\right)+f(n)$

其中：

• $a$：每次分解产生的子问题数量（$a\ge 1$）
• $b$：每个子问题的规模相对原问题的缩小比例（$b>1$，子问题规模为 $n/b$）
• $f(n)$：分解和合并阶段花费的代价（不含递归调用本身）

几个经典算法的递推关系：

算法	递推关系	参数解读
归并排序	$T(n)=2T(n/2)+O(n)$	分成 2 个子问题，每个规模 $n/2$，合并代价 $O(n)$
二分查找	$T(n)=T(n/2)+O(1)$	分成 1 个子问题，规模 $n/2$，无合并代价
快速排序（平均）	$T(n)=2T(n/2)+O(n)$	期望均匀分区时与归并排序同形
Karatsuba 大数乘法	$T(n)=3T(n/2)+O(n)$	分成 3 个子问题（而非 4 个），是优化的关键
暴力矩阵乘法	$T(n)=8T(n/2)+O(n^2)$	分成 8 个子问题，每个规模 $n/2$，合并 $O(n^2)$
Strassen 矩阵乘法	$T(n)=7T(n/2)+O(n^2)$	从 8 降到 7 个子问题，复杂度 $O(n^{2.807})$

这个递推关系的求解，正是主定理的职责。

---

第 2 章 递归树：直观推导复杂度的图形工具

2.1 递归树的思想

递归树是一种分析分治复杂度的图形化方法。它把递归调用展开成一棵树，根节点代表原问题，每个节点的子节点代表该层产生的子问题，叶节点代表基础情形。

每个节点标注的是该节点自身（不含子问题）的工作量，即 $f(n)$ 部分。整个树上所有节点工作量之和就是总时间复杂度。

2.2 以归并排序为例推导

归并排序的递推关系：$T(n)=2T(n/2)+cn$（$c$ 是合并一层的常数系数）。

第 0 层（根）:       cn
                   /    \
第 1 层:         cn/2    cn/2                   共 2 × cn/2 = cn
                /  \    /  \
第 2 层:      cn/4 cn/4 cn/4 cn/4              共 4 × cn/4 = cn
              ...
第 log₂n 层:  c  c  c  ...  c                  共 n × c = cn
（叶节点）

每一层的工作量之和都是 $cn$，树高为 ${\log }_{2}n$（因为每层规模缩小一半，到规模 1 需要 ${\log }_{2}n$ 层），因此：

$T(n)=cn\cdot {\log }_{2}n=O(n\log n)$

这个推导没有任何黑盒，每一步都是直观的累加。

2.3 以二分查找为例推导

二分查找的递推关系：$T(n)=T(n/2)+c$（$c$ 是常数，每次只需一次比较）。

第 0 层（根）:       c
                    |
第 1 层:            c
                    |
第 2 层:            c
                    ...
第 log₂n 层:        c（叶节点）

每层只有 1 个节点，每个节点工作量为 $c$，树高 ${\log }_{2}n$，因此：

$T(n)=c\cdot {\log }_{2}n=O(\log n)$

2.4 以 Karatsuba 乘法为例推导

Karatsuba 大数乘法的递推关系：$T(n)=3T(n/2)+cn$。

注意这里 $a=3$，$b=2$，每层的节点数以 3 倍增长，而每层每个节点的工作量以 $1/2$ 缩小：

第 0 层:       cn                              1 个节点，共 cn
第 1 层:    3 × cn/2                           3 个节点，共 3cn/2
第 2 层:    9 × cn/4                           9 个节点，共 9cn/4
...
第 k 层:    3^k × cn/2^k = (3/2)^k × cn       共 (3/2)^k × cn
...
第 log₂n 层: n^(log₂3) 个叶节点               共 Θ(n^(log₂3))

每层的工作量以公比 $3/2>1$ 递增，因此总复杂度由最后一层（叶节点）主导：

$T(n)=O(n^{{\log }_{2}3})\approx O(n^{1.585})$

注意这里的关键：当节点增速（$a=3$）大于规模缩小带来的代价减少速度（$b=2$ 对应 $1/b=1/2$），工作量就向叶节点倾斜，叶节点层成为主导。

2.5 三种模式的直觉总结

通过以上三个例子，我们可以归纳出递归树的三种形态：

形态	每层工作量变化	总复杂度主导	例子
每层相等	常数 $\times$ 第 0 层	每层均摊	归并排序
向根倾斜（叶节点减少）	递减几何级数	根节点（第 0 层）主导	（见下文主定理情形 3）
向叶倾斜（叶节点增加）	递增几何级数	叶节点主导	Karatsuba 乘法

---

第 3 章 主定理：三种情形的严格表述

主定理（Master Theorem）将递归树分析形式化为一个可直接套用的定理。它处理形如 $T(n)=aT(n/b)+f(n)$ 的递推关系（$a\ge 1$，$b>1$）。

3.1 叶节点工作量：关键参考量

主定理的核心是比较 $f(n)$（分解+合并代价）与叶节点的工作量。叶节点的工作量正比于叶节点的数量，而叶节点数量为：

$n^{{\log }_{b}a}$

推导：树高为 ${\log }_{b}n$，每层节点数乘以 $a$，因此叶节点数为 $a^{{\log }_{b}n}=n^{{\log }_{b}a}$（利用 $a^{{\log }_{b}n}=n^{{\log }_{b}a}$ 这个恒等式）。

${\log }_{b}a$ 是一个很重要的数，它描述了”子问题数量增长”相对于”子问题规模缩小”的净效应。下面三种情形本质上就是在比较 $f(n)$ 与 $n^{{\log }_{b}a}$ 的大小关系。

3.2 情形一：叶节点主导（$f(n)=O(n^{{\log }_{b}a-\epsilon })$）

条件：$f(n)$ 比 $n^{{\log }_{b}a}$ 多项式意义上更小，即存在常数 $\epsilon >0$ 使得 $f(n)=O(n^{{\log }_{b}a-\epsilon })$。

含义：分解+合并代价相对叶节点太小了，叶节点层的工作量主导。

结论：$T(n)=\Theta (n^{{\log }_{b}a})$

典型例子：Karatsuba 乘法，$a=3,b=2$，${\log }_{2}3\approx 1.585$，$f(n)=O(n)$。由于 $n<n^{1.585}$，满足情形一条件，所以 $T(n)=\Theta (n^{{\log }_{2}3})\approx \Theta (n^{1.585})$。

直觉：你在顶层节点做的工作，相比于叶节点层汇聚起来的总工作量来说，简直是九牛一毛。所有的代价都花在了”最底层”的基础情形上。

3.3 情形二：每层相等（$f(n)=\Theta (n^{{\log }_{b}a}\cdot {\log }^{k}n)$）

条件：$f(n)$ 与 $n^{{\log }_{b}a}$ 相等（在多对数因子意义上），即 $f(n)=\Theta (n^{{\log }_{b}a}\cdot {\log }^{k}n)$，其中 $k\ge 0$。

最常见的是 $k=0$ 的情形，即 $f(n)=\Theta (n^{{\log }_{b}a})$。

结论：$T(n)=\Theta (n^{{\log }_{b}a}\cdot {\log }^{k+1}n)$

最常见情形（$k=0$）：$T(n)=\Theta (n^{{\log }_{b}a}\cdot \log n)$

典型例子：归并排序，$a=2,b=2$，${\log }_{2}2=1$，$f(n)=\Theta (n)=\Theta (n^1)$。满足 $k=0$ 的情形二，所以 $T(n)=\Theta (n\log n)$。

二分查找，$a=1,b=2$，${\log }_{2}1=0$，$f(n)=\Theta (1)=\Theta (n^0)$。满足 $k=0$ 的情形二，所以 $T(n)=\Theta (n^0\cdot \log n)=\Theta (\log n)$。

直觉：每一层的工作量大致相同，总代价就是”工作量 × 层数”。

3.4 情形三：根节点主导（$f(n)=\Omega (n^{{\log }_{b}a+\epsilon })$）

条件：$f(n)$ 比 $n^{{\log }_{b}a}$ 多项式意义上更大，即存在常数 $\epsilon >0$ 使得 $f(n)=\Omega (n^{{\log }_{b}a+\epsilon })$；同时需要满足正则条件：对足够大的 $n$，存在常数 $c<1$ 使得 $a\cdot f(n/b)\le c\cdot f(n)$（合并代价在递归过程中不会反常增长）。

结论：$T(n)=\Theta (f(n))$

典型例子：假设有个算法满足 $T(n)=2T(n/2)+O(n^2)$（分成 2 个子问题，但合并代价是 $n^2$）。这里 ${\log }_{2}2=1$，$f(n)=O(n^2)=\Omega (n^{1+1})$，满足情形三，所以 $T(n)=\Theta (n^2)$。

直觉：顶层节点的工作量远大于叶节点，合并阶段的代价主导了整个算法。你在顶层花了大部分时间，下面的子问题虽然多但是都很小。

主定理的适用边界

主定理只能处理子问题规模为 $n/b$（等比缩小）的情形。如果子问题规模是 $n-c$（减法递推，如 Fibonacci）或不均等分割，主定理不适用，需要手动用递归树或换元法求解。此外，主定理还有若干”灰色地带”：例如 $f(n)=n/\log n$ 时（情形一和二之间），主定理无法直接给出结论。

3.5 三种情形速查表

情形	条件	结论	典型算法
情形一（叶主导）	$f(n)=O(n^{{\log }_{b}a-\epsilon })$	$T(n)=\Theta (n^{{\log }_{b}a})$	Karatsuba、Strassen
情形二（每层相等）	$f(n)=\Theta (n^{{\log }_{b}a})$	$T(n)=\Theta (n^{{\log }_{b}a}\log n)$	归并排序、二分查找
情形三（根主导）	$f(n)=\Omega (n^{{\log }_{b}a+\epsilon })$ + 正则条件	$T(n)=\Theta (f(n))$	多数分治合并代价较高时

---

第 4 章 分治算法通用模板

4.1 代码框架

掌握了理论之后，我们来看分治算法的通用代码框架：

/**
 * 分治算法通用框架
 *
 * @param problem 当前要解决的问题（规模为 n）
 * @return 当前问题的解
 */
T divideAndConquer(Problem problem) {
    // 基础情形：当问题规模足够小时，直接求解
    if (problem.size() <= THRESHOLD) {
        return solveDirectly(problem);
    }
 
    // 第一步：分解——将问题分解为若干子问题
    List<Problem> subProblems = divide(problem);
 
    // 第二步：递归征服——递归求解每个子问题
    List<T> subResults = new ArrayList<>();
    for (Problem sub : subProblems) {
        subResults.add(divideAndConquer(sub));
    }
 
    // 第三步：合并——将子问题的解合并为原问题的解
    return combine(subResults);
}

这个框架中，三个方法（divide、solveDirectly、combine）需要针对具体问题实现，其余结构是固定的。

面试中识别分治适用性的信号：

1. 问题可以自然地拆分为独立子问题（子数组、子树、子字符串等）
2. 子问题与原问题形式相同（满足递归结构）
3. 合并子问题的解有明确且高效的方式
4. 暴力解法复杂度是 $O(n^2)$ 或更高，而分治有望降到 $O(n\log n)$

4.2 从归并排序看三要素落地

归并排序是分治思想最清晰的实现，值得逐行分析其三要素：

void mergeSort(int[] arr, int left, int right) {
    // ① 基础情形：只有一个或零个元素，本身就是有序的
    if (left >= right) return;
 
    // ② 分解：取中点，将数组一分为二
    //    left + (right - left) / 2 防止 (left + right) 溢出
    int mid = left + (right - left) / 2;
 
    // ③ 递归征服：先排左半段，再排右半段
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
 
    // ④ 合并：将两个有序段合并为一个有序段
    merge(arr, left, mid, right);
}
 
void merge(int[] arr, int left, int mid, int right) {
    // 将 arr[left..mid] 和 arr[mid+1..right] 合并
    // 这两段分别是有序的（由递归保证）
    int[] temp = new int[right - left + 1];
    int i = left, j = mid + 1, k = 0;
 
    while (i <= mid && j <= right) {
        // 取两段中较小的放入临时数组
        // 注意 <= 而非 <：相等时取左边，保证排序的稳定性
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
 
    // 处理剩余部分（最多只有一个 while 会执行）
    while (i <= mid)  temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];
 
    // 将临时数组的结果写回原数组
    for (int t = 0; t < temp.length; t++) {
        arr[left + t] = temp[t];
    }
}

三要素分析：

• 分解：mid = left + (right - left) / 2，$O(1)$ 代价，平均将数组对半切
• 征服：两次递归调用，每次规模 $n/2$
• 合并：merge 函数，$O(n)$ 代价，双指针线性扫描

对应主定理：$a=2,b=2,f(n)=O(n)$，${\log }_{b}a={\log }_{2}2=1$，$f(n)=\Theta (n^1)$，满足情形二，$T(n)=O(n\log n)$。

4.3 分治算法的常见”陷阱”

理解了框架之后，实际编码时有几个高频错误需要特别注意：

陷阱 1：基础情形处理不完整

最常见的问题是遗漏基础情形，或者基础情形的条件写反。例如归并排序的基础情形是 if (left >= right) return，如果写成 if (left > right) return，当 left == right（单元素）时会继续递归，导致无限循环。

陷阱 2：分解时下标越界

mid = (left + right) / 2 在 left 和 right 都很大时会整数溢出（两者之和超过 Integer.MAX_VALUE）。应该写 mid = left + (right - left) / 2，这是一个面试必须展示的细节。

陷阱 3：合并时破坏原数组

归并排序在合并阶段需要临时空间，如果试图原地合并（不使用额外数组），在数组上操作会很复杂（原地归并的最优算法本身就需要 $O(n\log n)$ 代价）。一般做法是用临时数组再回写。

陷阱 4：不必要的重复分割

有时候一个分治解法会把同一个子问题计算多次（子问题有重叠），这时就应该考虑 memoization 或直接改用动态规划。分治的前提是子问题独立。

---

第 5 章 分治法的应用场景与识别方法

5.1 分治的典型应用场景

分治算法在面试中出现的形式，大体可以归为以下几类：

1. 排序与选择类

归并排序、快速排序、快速选择（Kth largest element）——这类问题的特点是”对数组分段，分别处理，再合并”，是最经典的分治形式。详见本专栏第 02、03 篇。

2. 逆序对与统计类

逆序对（Count Inversions）、区间内满足条件的对数（LeetCode 315、493、327）——这类问题的特点是”在合并阶段同时统计跨越两段的配对”，是归并分治的扩展。详见第 02 篇。

3. 树形结构类

二叉树的分治（最大深度、重建、直径）——树天然具有递归结构，左子树和右子树就是两个独立的子问题，分治思想在树上几乎是”免费”的。详见第 05 篇。

4. 数学计算类

大数乘法（Karatsuba）、矩阵快速幂、多项式乘法（FFT）——这类问题通过代数变形将 $a$ 个子问题降为 $a^{\prime }<a$ 个，从而降低复杂度。

5. 最优化类

最大子数组（LeetCode 53）、最近点对问题——通过”分段处理 + 跨段特殊处理”，将 $O(n^2)$ 的暴力解降到 $O(n\log n)$。详见第 04 篇。

5.2 面试中如何快速识别分治

在面试中，以下信号提示这道题可能适合用分治：

1. 问题具有自然的”中点”划分：如数组中点、链表中点、二叉树根节点
2. 子问题与原问题结构相同：如”在子数组中找最大值”和”在整个数组中找最大值”形式一样
3. 存在”跨越左右两部分”的特殊情况：如最大子数组的跨越型子数组，逆序对中跨越两段的逆序对，这是分治”合并”阶段需要处理的内容
4. 暴力是 $O(n^2)$：如果暴力枚举所有对是 $O(n^2)$，而通过排序/分治可以降到 $O(n\log n)$，这通常值得考虑

设计哲学：分治 vs 其他范式

• 分治 vs 动态规划：分治要求子问题独立无重叠；DP 处理有重叠的子问题（用 memo 避免重复计算）。如果你发现递归中同一个子问题被多次求解，应该加 memo（此时变成了”带 memo 的递归”，即自顶向下的 DP）。
• 分治 vs 贪心：分治是”分解后再合并”，每个子问题都要求解；贪心是”每步做局部最优选择”，不分解子问题，不回溯。如果一个问题每步的最优选择独立于子问题的结构，用贪心；否则用分治或 DP。
• 分治 vs 递归：所有分治算法都用递归实现，但不是所有递归都是分治。分治必须满足”分解为独立子问题”且”通过合并子问题的解得到原问题的解”，单纯的递推（如 Fibonacci）不是分治。

5.3 一个综合例子：最接近点对问题

最接近点对问题（Closest Pair of Points）是分治算法中最经典也最复杂的例子之一，虽然它不是 LeetCode 高频题，但理解它有助于深刻体会分治的”跨越处理”模式：

问题：在平面上给定 $n$ 个点，找出欧氏距离最近的两个点。

暴力：枚举所有 $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ 对，$O(n^2)$。

分治思路：

1. 将所有点按 $x$ 坐标排序，取中线 $x=median$ 将点集分成左右两半
2. 递归求左半部分的最近距离 $d_L$，和右半部分的最近距离 $d_R$
3. 令 $d=\min (d_L,d_R)$，此时最近点对要么都在左半部分，要么都在右半部分，要么跨越中线
4. 跨越中线的情形：只需检查距中线 $d$ 以内的所有点（称为”带状区域”），且每个点只需与带状区域内的另外 $O(1)$ 个点比较（几何论证）
5. 整体复杂度：$T(n)=2T(n/2)+O(n)=O(n\log n)$

这个例子的精妙之处：步骤 4 中”带状区域内每个点只需检查 $O(1)$ 个邻居”——这是几何性质（在 $d\times 2d$ 的矩形内不可能有超过 8 个点的距离都超过 $d$）给我们带来的礼物。分治的合并代价从 $O(n^2)$（暴力枚举带状区域内所有对）降到了 $O(n)$，这才让整体复杂度降至 $O(n\log n)$。

---

第 6 章 分治法的时间复杂度小结与主定理速用

6.1 面试中的主定理速用流程

面试中遇到分治算法的复杂度分析，三步即可得出结论：

第一步：写出递推关系 $T(n)=aT(n/b)+f(n)$，明确 $a$、$b$、$f(n)$。

第二步：计算 $c={\log }_{b}a$（这是叶节点层工作量的指数）。

第三步：比较 $f(n)$ 与 $n^c$ 的大小：

• 若 $f(n)<n^c$（多项式意义），取情形一，$T(n)=\Theta (n^c)$
• 若 $f(n)\approx n^c$（多项式意义相等），取情形二，$T(n)=\Theta (n^c\log n)$
• 若 $f(n)>n^c$（多项式意义），取情形三，$T(n)=\Theta (f(n))$

第四步（检验）：对情形三，验证正则条件成立（$a\cdot f(n/b)\le c\cdot f(n)$，对多数多项式自动成立）。

6.2 面试常见递推关系速查

递推关系	$a$	$b$	${\log }_{b}a$	$f(n)$	情形	$T(n)$
$T(n)=2T(n/2)+O(n)$	2	2	1	$n^1$	二（相等）	$O(n\log n)$
$T(n)=T(n/2)+O(1)$	1	2	0	$n^0$	二（相等）	$O(\log n)$
$T(n)=3T(n/2)+O(n)$	3	2	1.585	$n^1<n^{1.585}$	一（叶主导）	$O(n^{1.585})$
$T(n)=2T(n/2)+O(n^2)$	2	2	1	$n^2>n^1$	三（根主导）	$O(n^2)$
$T(n)=4T(n/2)+O(n^2)$	4	2	2	$n^2$	二（相等）	$O(n^2\log n)$
$T(n)=8T(n/2)+O(n^2)$	8	2	3	$n^2<n^3$	一（叶主导）	$O(n^3)$
$T(n)=7T(n/2)+O(n^2)$	7	2	2.807	$n^2<n^{2.807}$	一（叶主导）	$O(n^{2.807})$

---

第 7 章 本文核心结论与专栏预告

7.1 核心结论

1. 分治的正确性依赖子问题独立性：子问题有重叠则改用 DP，子问题无法独立分解则考虑其他方法
2. 递归树是复杂度分析的直觉工具：关注”每层总工作量”的趋势（递增/相等/递减），就能判断复杂度的主导项
3. 主定理是递归树的形式化：三种情形分别对应叶主导、均匀分布、根主导三种递归树形态
4. 分解代价和合并代价是关键变量：降低 $a$（减少子问题数量，如 Karatsuba）或降低 $f(n)$（减少合并代价，如带状区域剪枝）是优化分治算法的核心手段

7.2 专栏后续安排

本篇讲完了分治的理论骨架，后续几篇进入实战：

• 第 02 篇：归并分治的经典扩展——逆序对问题（LeetCode 315、LeetCode 493）。归并排序的”合并”阶段不只能排序，还能在合并时统计跨段配对，这是一类极重要的面试模式。

• 第 03 篇：快速排序的分治框架——分区操作的三种变体（Lomuto、Hoare、三路分区），以及从快速排序自然延伸出的快速选择算法（LeetCode 215）。

• 第 04 篇：最大子数组问题——$O(n\log n)$ 的分治解法与 $O(n)$ 的 Kadane 算法，两种视角理解同一个问题（LeetCode 53、LeetCode 152、LeetCode 918）。

• 第 05 篇：分治在二叉树上的应用——树的递归结构天然适合分治，重建二叉树和树的最长路径是面试高频考点（LeetCode 105、LeetCode 106、LeetCode 543、LeetCode 124）。