2.7 分治算法设计

第二卷走到尾声。前六篇我们用分治解决了排序（快排）、选择（线性选择）、几何（最近点对、凸包）、代数（Strassen、FFT）五大类问题。你可能已经隐约感觉到，它们背后共享着同一套设计结构。这一篇，我把这套结构提炼出来——它就是分治（divide and conquer）这个设计范式的通用法则。读完这篇，你面对一个新问题时，应该能判断"它适不适合用分治、该怎么分"。

1.分治的三步范式

所有分治算法都遵循同一个三步骨架：

第一步·分（Divide）。 把原问题切成几个规模更小的子问题。怎么切？这是分治设计的核心抉择——按位置对半切（归并、最近点对）、按值划分（快排、选择）、按结构拆分（Strassen 的子矩阵、FFT 的奇偶次项）。

第二步·治（Conquer）。 递归地解决每个子问题。当子问题小到一定程度（基底），直接求解。

第三步·合（Combine）。 把子问题的解合并成原问题的解。这一步的代价，往往决定了整个算法的复杂度。

这三步里，"怎么分"和"怎么合"是设计的着力点。回顾第二卷，你会发现分治算法大致分两类：一类"分得费劲、合得轻松"，一类"分得轻松、合得费劲"。

2.两种姿态：重分轻合 vs 轻分重合

第二卷的所有算法，都能归到这两种姿态之一：

姿态一·重分轻合（划分型）。 代表：快速排序、线性选择。它们的"分"（partition，划分）是重头戏——精心选基准、让元素各就各位；但"合"几乎不费力，因为划分时元素已经到位，两侧递归完直接就是答案。这类算法复杂度对"分得均不均"敏感（快排最坏 $O(n^2)$ ）。

姿态二·轻分重合（合并型）。 代表：归并排序、最近点对、Strassen、FFT。它们的"分"很机械（按位置对半切），但"合"是重头戏——归并排序的归并 $\Theta(n)$ 、最近点对的窄带处理、Strassen 的 7 个子乘积组合、FFT 的蝶形合成。这类算法复杂度稳定（通常 $O(n\log n)$ ），因为分得均匀。

这个对照我们在 2.1 快排 vs 归并时已经点过，现在它上升到一般法则：设计分治算法时，先想清楚"难活放在分还是合"，两者各有适用场景。 划分型适合"元素有内在顺序、能按值分开"的问题；合并型适合"问题能干净对半切、子结果能线性合并"的问题。

3.分治复杂度：主定理预告

分治算法的复杂度几乎都靠递归关系 $T(n)=aT(n/b)+f(n)$ 表达：分成 $a$ 个规模 $n/b$ 的子问题，合并代价 $f(n)$ 。这一卷我们每次都用递归树（2.2、2.5）来解，但第四卷的主定理（4.2）会给这类递归一个通用解法，不用每次画树。先记住几个本卷出现的经典：

归并/最近点对： $T(n)=2T(n/2)+O(n)=O(n\log n)$ 。
二分查找： $T(n)=T(n/2)+O(1)=O(\log n)$ （只递归一边）。
Strassen： $T(n)=7T(n/2)+O(n^2)=O(n^{\log_2 7})$ （减少分支数 $a$ 降指数）。
FFT： $T(n)=2T(n/2)+O(n)=O(n\log n)$ 。

关键直觉：递归分支数 $a$ 决定指数 $\log_b a$ ，合并代价 $f(n)$ 和它比较决定总阶。想让算法更快，要么减小 $a$ （Strassen 的 7 vs 8），要么让 $f(n)$ 更便宜。这是分治优化的两条根本路径。

4.分治什么时候用，什么时候别用

不是所有问题都适合分治。判断一个新问题适不适合分治，看三个条件：

条件一：能切成独立子问题吗？ 子问题之间应该尽量独立、互不影响。归并排序左半右半独立；但有些问题（比如全局最优有强耦合）切了之后子问题不独立，分治就难用。

条件二：子问题和原问题同构吗？ 子问题应该是原问题的"缩小版"——同样的形式、更小的规模。这保证能递归。FFT 的子问题（在 $n/2$ 个点上求值）和原问题（在 $n$ 个点上求值）同构，所以能递归。

条件三：合并代价可控吗？ 合并 $f(n)$ 不能太贵，否则总复杂度被它主导。如果合并本身是 $O(n^2)$ ，那 $T(n)=2T(n/2)+O(n^2)=O(n^2)$ ，没省。分治的收益，本质上来自"合并比朴素解整个问题便宜"。

满足这三条，分治多半有用武之地。不满足，就得考虑别的范式——第三卷的贪心和动态规划。

5.第二卷的统一图景

把第二卷六篇放一起，你会看到一个震撼的统一图景：

排序、选择、几何最近点对、几何凸包、矩阵乘法、多项式乘法——这些表面上天差地别的问题，居然共享同一种设计结构：分治。

这是第二卷最想让你带走的东西。算法不是 100 个孤立的技巧，而是少数几种设计范式在不同问题上的反复应用。分治就是其中之一。到了第十一卷，我们会把分治连同贪心、动态规划、归约、对偶等一起，提炼成一套面对任何新问题都能用的设计工具箱。

6.练习

Q1. 归并排序和快速排序都是分治，但"分"和"合"的重心不同。各属于哪种姿态？这如何影响它们的最坏复杂度？

归并是"轻分重合"（机械对半切、重头戏在 $\Theta(n)$ 的归并），因为分得均匀，最坏也稳定 $O(n\log n)$ 。快排是"重分轻合"（重头戏在按基准划分、合几乎不费力），复杂度对划分是否均匀敏感，最坏退化 $O(n^2)$ （划分极度不均时）。这是"分合重心在哪"直接影响最坏复杂度的典型例子。

Q2. 判断分治适不适合一个新问题，看哪三个条件？

① 能切成独立子问题（子问题间互不耦合）；② 子问题与原问题同构（同形式更小规模，保证可递归）；③ 合并代价可控（合并 $f(n)$ 不能太贵，否则被合并主导、白分治）。三者满足分治通常可行，否则考虑贪心/动态规划等其他范式。

Q3.（思考题） Strassen 把子乘积从 8 减到 7，FFT 利用单位根把求值点压半。这两者背后的共同原理是什么？

都是减少递归分支数 $a$ 来降低复杂度指数。Strassen： $8\to7$ 让指数从 $\log_2 8=3$ 降到 $\log_2 7\approx 2.807$ ；FFT：靠单位根的折半性质，让子问题（偶/奇次项）的求值点数减半（ $n\to n/2$ ），相当于 $a$ 不变但每层代价被性质压缩。共同原理：分治的复杂度由 $T(n)=aT(n/b)+f(n)$ 决定，减小 $a$ （分支数）或压缩 $f$ （合并代价）是加速的两条根本路径。

分治是"切分→递归→合并"的三步范式，分治算法分"重分轻合"（划分型，如快排）和"轻分重合"（合并型，如归并）两种姿态。它的复杂度由递归关系 $T(n)=aT(n/b)+f(n)$ 决定，减小分支数 $a$ 或合并代价 $f$ 是加速根本。第二卷的统一图景是：排序、选择、几何、矩阵、多项式乘法共享分治结构——算法是少数范式在不同问题上的反复应用。第二卷到此结束，第一学习阶段（理解算法）圆满收尾。下一卷我们进入最优化问题的两条主线——贪心与动态规划。