《Hello 算法》分治法总结：以“分而治之”的递归策略设计高效算法

本篇基于《Hello 算法》（hello-algo）日文版文档 分治法总结，系统梳理分治法（divide and conquer）的两大阶段、判断标准与提效原理，并结合仓库中 Python 源码，完整讲解合并排序、递归二分查找、二分树构建与汉诺塔四个典型问题中“分”与“治”的具体落地方式。读完后，你将掌握一套可复用的分析框架：判断一个问题是否适合分治、如何设计分割方案、如何推导其时间复杂度，并能直接对照源码理解各算法的递归实现细节。

分治法的两个阶段：“分”与“治”

分治法（divide and conquer）意为“把问题分开，再把它们统管起来”，是《Hello 算法》中介绍的一种非常重要且通用的算法设计策略。其核心结论可以概括为：分治法是一种通用的算法设计策略，由“分”（分割）与“治”（合并）两个阶段构成，通常基于递归来实现（详见 分治法主文档）。

两个阶段的具体含义为：

1. 分（分割阶段）：把原问题递归地分解为两个或更多子问题，直到达到最小的、可以直接求解的子问题为止；
2. 治（合并阶段）：从已知解的最小问题出发，自下而上地合并各子问题的解，最终构造出原问题的解。

以合并排序（Merge Sort）为例，这一策略体现得非常直观：

• 分：把原数组（原问题）递归地分割为两个子数组（子问题），直到每个子数组中只剩 1 个元素；
• 治：把已排好序的子数组（子问题的解）自下而上合并，得到排好序的原数组（原问题的解）。

仓库中的 Python 实现 merge_sort.py 完整对应了这两个阶段：merge_sort() 函数先通过 mid = (left + right) // 2 计算中点，再分别递归排序左右两个子区间（“分”），最后调用 merge() 将两个有序子数组合并（“治”）。其中递归终止条件 if left >= right: return 正是“子数组长度变为 1 时停止分割”的代码表达；而 merge() 中使用临时数组 tmp 双指针比较、再回写原数组的写法，保证了合并过程是稳定排序，单层合并耗时为 O(k)（k 为区间长度）。

如何判断一个问题适合分治法

总结文档给出的判断标准有三条，可以作为工程实践中评估算法方案的检查清单：

1. 问题可分解：原问题可以分解为规模更小但结构相似的子问题，且能以同样的方式继续递归分割；
2. 子问题相互独立：子问题之间没有重叠、没有相互依赖，可以独立求解；
3. 子问题的解可合并：原问题的解可以由子问题的解合并得到。

对照合并排序验证：数组可递归地分为两个子数组（标准 1 满足）；两个子数组可以独立排序（标准 2 满足）；两个有序子数组可以合并为一个有序数组（标准 3 满足）。

值得注意的是，后文会讲到的几个问题在“可合并性”上存在差异：二分查找不需要合并步骤，而汉诺塔问题的“合并”是按特定顺序依次求解。这正是总结文档中反复强调“判断标准”的原因——三条标准是灵活应用的框架，而非机械的模板。

为什么分治法能提高效率

总结文档指出，引入分治法不仅能解决问题，在多数情况下还能提升算法效率：一方面减少了操作次数，另一方面分割后便于系统进行并行优化。索特算法中，快速排序、归并排序和堆排序之所以比选择排序、冒泡排序和插入排序更快，正是应用了分治策略。

操作次数优化：一次不等式推导

以冒泡排序为例：排序长度为 n 的数组需要 O(n²) 时间。若把数组一分为二，分割需要 O(n)，排序两个子数组各需 O((n/2)²)，合并需要 O(n)，总时间为：

$$O\left(n + \left(\frac{n}{2}\right)^2 \times 2 + n\right) = O\left(\frac{n^2}{2} + 2n\right)$$

比较分割前后（不等式左、右两边分别是分割前、后的操作总量）：

$$n^2 - \frac{n^2}{2} - 2n = n(n - 4) > 0 \quad \Rightarrow \quad n > 4$$

也就是说，当 n > 4 时，分割后的操作数更少，排序效率更高。但要清醒地看到：此时的时间复杂度仍是二次的 O(n²)，只是常数项变小了。

进一步的两个方向（总结文档原文脉络）：

• 持续分割到最小粒度：继续从中间把子数组一分为二，直到只剩 1 个元素——这就是归并排序，时间复杂度 O(n log n)；
• 增加分割点的数量：把原数组均匀地分成 k 个子数组——这与桶排序的思路非常接近，理论上可达 O(n + k)，特别适合对海量数据进行排序。

并行计算优化

分治法生成的子问题彼此独立，通常可以并行求解。因此分治法不仅降低了算法本身的时间复杂度，还对操作系统的并行优化有利：在多线程或多处理器环境下，多个子问题可被同时处理，更充分地利用算力资源，显著缩短整体执行时间。典型例子是桶排序：把海量数据均匀分布到各个桶中，各桶的排序分散到不同计算单元执行，完成后再合并结果。这一特性使分治法天然适配 GPU、分布式计算等场景。

分治查找策略：从穷举到二分查找

总结文档将查找算法分为两类，并给出关键结论：相比穷举查找，适应性查找更高效；时间复杂度为 O(log n) 的查找算法，通常基于分治法实现。

• 穷举查找：通过遍历数据结构实现，时间复杂度 O(n)；
• 适应性查找：利用特定的数据结构或先验信息，时间复杂度可达 O(log n)，甚至 O(1)。

二分查找在分治视角下的三个判断（引自 分治查找策略）：

• 问题可分解：原问题“在数组中查找”被分解为子问题“在数组的一半中查找”，通过比较中点元素与目标元素来完成分割；
• 子问题独立：每一轮只处理一个子问题，不受其他分支影响；
• 无需合并子问题的解：二分查找的目标是找到某个特定元素，子问题一旦解决，原问题也就解决了——因此二分查找不含“治”（合并）的步骤，这与归并排序形成鲜明对比。

分治能提升查找效率的本质在于：穷举查找每轮只能排除一个候选，而基于分治的查找每轮能排除一半候选。这也解释了为何二分查找树、AVL 树等树形结构的各类操作时间复杂度都是 O(log n)。

递归实现的二分查找

书中先给出了基于迭代（循环）的二分查找实现，总结文档对应的代码则是基于分治（递归）的实现。设查找区间为 [i, j]，将对应的子问题记作 f(i, j)，从原问题 f(0, n-1) 出发：

1. 计算区间 [i, j] 的中点 m，并据此排除区间的一半；
2. 递归求解规模减半的子问题，候选为 f(i, m-1) 或 f(m+1, j)；
3. 重复上述步骤，直到找到 target 或区间为空。

Python 实现见 binary_search_recur.py，递归函数 dfs() 与上述三步一一对应：

def dfs(nums: list[int], target: int, i: int, j: int) -> int:
    """二分查找：求解问题 f(i, j)"""
    # 区间为空则目标元素不存在，返回 -1
    if i > j:
        return -1
    # 计算中点索引 m
    m = (i + j) // 2
    if nums[m] < target:
        # 递归求解子问题 f(m+1, j)
        return dfs(nums, target, m + 1, j)
    elif nums[m] > target:
        # 递归求解子问题 f(i, m-1)
        return dfs(nums, target, i, m - 1)
    else:
        # 找到目标元素，返回其索引
        return m

其中 i > j 的判空条件正是“子问题为空即终止递归”的基本情形；主函数 binary_search() 则以 dfs(nums, target, 0, n - 1) 启动原问题。运行驱动代码（target = 6, nums = [1, 3, 6, 8, 12, 15, 23, 26, 31, 35]）可验证返回目标元素 6 的索引 2。

构建二分树：用索引区间切分左右子树

总结文档对此问题的概括是：构建二分树的问题中，树的构建（原问题）可以被分解为左子树与右子树的构建（子问题），通过分割前序遍历与中序遍历的索引区间来实现。

判定为分治问题

给定前序遍历 preorder 与中序遍历 inorder（树中无重复值），要构建出该二分树并返回根节点（问题描述见 构建二分树问题）：

• 可分解：原问题分解为“构建左子树”“构建右子树”两个子问题，外加初始化根节点一步；各子树以同样的方式继续分割，直到空子树为止；
• 独立：构建左子树时只看对应左子树的那部分遍历序列，右子树同理，两者无重叠；
• 可合并：左右子树建成后，将它们挂到根节点上即得原问题的解。

如何分割子树：前序与中序的切分规则

按定义，两种遍历序列都可以分成三段：

• 前序遍历：[ 根节点 | 左子树 | 右子树 ]，例如 [ 3 | 9 | 2 1 7 ]；
• 中序遍历：[ 左子树 | 根节点 | 右子树 ]，例如 [ 9 | 3 | 1 2 7 ]。

分割步骤为：

1. 前序遍历的首元素 3 就是根节点的值；
2. 在中序遍历中查找根节点 3 的位置，据此把 inorder 切分为 [ 9 | 3 | 1 2 7 ]；
3. 由切分结果得知左右子树节点数分别为 1 和 3，进而把 preorder 切分为 [ 3 | 9 | 2 1 7 ]。

为精确描述各部分占用的索引区间，引入三个变量：

• i：当前树的根节点在 preorder 中出现的索引；
• m：当前树的根节点在 inorder 中出现的索引；
• [l, r]：当前树在 inorder 中占据的索引区间。

各部分对应的索引区间如下表：

	根节点在 preorder 中的索引	子树在 inorder 中的索引区间
当前树	i	[l, r]
左子树	i + 1	[l, m-1]
右子树	i + 1 + (m - l)	[m+1, r]

其中右子树根节点索引中的 (m-l) 表示“左子树的节点数”。

源码实现与复杂度分析

build_tree.py 中的 dfs() 函数与上表完全对应：

def dfs(preorder, inorder_map, i, l, r):
    """构建二分树：分治"""
    # 子树区间为空则结束
    if r - l < 0:
        return None
    # 初始化根节点
    root = TreeNode(preorder[i])
    # 求出 m 以切分左右子树
    m = inorder_map[preorder[i]]
    # 子问题：构建左子树
    root.left = dfs(preorder, inorder_map, i + 1, l, m - 1)
    # 子问题：构建右子树
    root.right = dfs(preorder, inorder_map, i + 1 + m - l, m + 1, r)
    return root

注意主函数 build_tree() 中构建哈希表 inorder_map = {val: i for i, val in enumerate(inorder)} 的技巧：它把“在中序遍历中查找根节点位置”从 O(n) 线性查找降为 O(1) 哈希查询，避免每层递归都重复扫描，这是保证总时间 O(n) 的关键优化。

复杂度推导（与文档一致）：

• 时间 O(n)：树中共 n 个节点，每个节点对应 dfs() 的一次执行、耗时 O(1)（借助哈希表），合计 O(n)；
• 空间 O(n)：哈希表占用 O(n)；最坏情况下二分树退化为链表，递归深度达到 n，需要 O(n) 的调用栈空间。

汉诺塔：从 n 到两个 n-1 加一个 1

汉诺塔问题采用了与前文不同的分解策略：归并排序和构建二分树都是把原问题分解为规模减半的两个子问题，而汉诺塔是把规模 n 的原问题分解为两个规模 n-1 的子问题加一个规模 1 的子问题（问题描述与规则见 汉诺塔问题）。

设规模 i 的汉诺塔问题为 f(i)，即把 i 个圆盘从柱子 A 移到柱子 C，且满足：一次只能移动一个圆盘；只能从柱顶取放；小圆盘必须始终压在大圆盘之上。

从基本情形归纳递归策略

• f(1)：只有一个圆盘，直接从 A 移到 C；
• f(2)：需要借助柱子 B 中转——先把小盘移到 B，再把大盘移到 C，最后把小盘从 B 移到 C。这里出现了“目标柱”与“辅助柱”的概念；
• f(3)：把 A 顶上的两个圆盘看成一个整体：① 以 B 为目标柱、C 为辅助柱，把两个圆盘从 A 移到 B（这正是 f(2)）；② 把 A 上剩下的 1 个圆盘直接移到 C（f(1)）；③ 以 C 为目标柱、A 为辅助柱，把两个圆盘从 B 移到 C（又是一个 f(2)）。

由此得到通用策略：原问题 f(n) = 子问题 f(n-1) × 2 + 子问题 f(1) × 1，三个子问题依次求解：

1. 借助 C，把 n-1 个圆盘从 A 移到 B；
2. 把剩下的 1 个圆盘从 A 直接移到 C；
3. 借助 A，把 n-1 个圆盘从 B 移到 C。

其中两个 f(n-1) 子问题以同样的方式继续递归分解，直到最小的子问题 f(1)（一次移动即可完成）。

源码实现与复杂度分析

hanota.py 中定义递归函数 dfs(i, src, buf, tar)，语义是“借助辅助柱 buf，把 src 顶上的 i 个圆盘移到目标柱 tar”：

def dfs(i: int, src: list[int], buf: list[int], tar: list[int]):
    """求解汉诺塔问题 f(i)"""
    # 若 src 只剩 1 个圆盘，直接移到 tar
    if i == 1:
        move(src, tar)
        return
    # 子问题 f(i-1)：借助 tar 把 src 顶部的 i-1 个圆盘移到 buf
    dfs(i - 1, src, tar, buf)
    # 子问题 f(1)：把 src 剩下的 1 个圆盘移到 tar
    move(src, tar)
    # 子问题 f(i-1)：借助 src 把 buf 顶部的 i-1 个圆盘移到 tar
    dfs(i - 1, buf, src, tar)

注意三行递归/移动调用恰好对应上文的三步策略，且 buf、tar 参数在两次递归中互换位置——这正是“目标柱与辅助柱角色互换”的代码体现。用列表的末尾表示柱顶（pop() 取盘、append() 放盘）使得移动操作 O(1) 完成。

从源码结构看，dfs() 每次调用最多展开为两次规模为 i-1 的递归调用，形成一棵高度为 n 的递归树，节点总数约为 2ⁿ。因此时间复杂度为 O(2ⁿ)，空间复杂度为 O(n)（递归调用栈的最大深度为 n）。

书中还引了一个著名的传说作注脚：古印度寺庙的僧侣们日夜移动 64 个金盘，即使每秒移动一次，也需要约 2⁶⁴ ≈ 1.84×10¹⁹ 秒（约 5850 亿年），远超宇宙现有年龄——这也直观解释了为何 O(2ⁿ) 的指数级复杂度在大规模输入下是“不可接受”的，反衬出分治法通过合理设计分解方式降低复杂度的价值。

总结：分治法“润物细无声”

对照 summary.md 的要点，可以归纳出分治法在《Hello 算法》中的三条主线：

作为算法设计策略，分治法适用于满足“可分解、子问题独立、解可合并”三个标准的问题。典型应用包括：

• 最近点对问题：先把点集一分为二，分别求各部分内部的最近点对，最后求跨越两部分的最近点对；
• 大整数乘法：如 Karatsuba 算法，把大整数乘法分解为若干小整数的乘法与加法；
• 矩阵乘法：如 Strassen 算法，把大矩阵乘法分解为若干小矩阵的乘法与加法；
• 汉诺塔问题：如上节所示，典型的递归分治应用；
• 求逆序数：前大后小的数对构成逆序，可借助分治思想、用归并排序求解。

作为数据结构与算法设计的基石，分治法被广泛运用于：二分查找、归并排序、快速排序、桶排序、树形结构（二分查找树、AVL 树、红黑树、B 树、B+ 树）、堆（堆是特殊的完全二分树，插入、删除、堆化等操作中蕴含分治思想）、以及哈希表的部分冲突解决方案（如链地址法中把较长的链表转换为红黑树以提升查询效率）。

作为查找效率的加速器，O(log n) 的适应性查找（二分查找、树形结构）本质上都是分治策略，每一轮排除一半候选是其快于 O(n) 穷举查找的根本原因。

从本章的四个代码实现（合并排序、递归二分查找、构建二分树、汉诺塔）也能印证：分治法并不是“静悄悄地滋养万物”式的玄学，而是一套可以落到代码层面的工程方法——定义子问题 f(i, j)、写出基本情形、设计分割与合并（或依次求解）规则、推导递归树的规模，四步走完，算法的骨架与复杂度分析便已就位。仓库同时提供 C、C++、C#、Go、Java、JavaScript、Kotlin、Ruby、Rust、Swift、TypeScript、Dart 等语言的同构实现（位于 codes/ 目录下各语言章节中），可供读者对照不同语言的递归写法；章末还有 课后练习 供进一步巩固。