分治算法：化整为零的智慧
分治算法，说白了就是「分而治之」。我刚开始学算法时，总觉得这名字挺唬人。后来做项目多了才发现，这其实就是我们日常解决问题的本能——遇到一个大问题，先拆成几个小问题，小问题还解决不了？那就再拆。直到拆成一眼就能看穿的小块，然后逐个击破，最后把结果拼起来。
你想想看，这跟管理一个团队是不是很像？CEO 不会亲自去写每一行代码，而是把任务拆解，交给各个部门去完成。分治算法也是这个道理。
分治的三步曲
分治算法有三个核心步骤，我习惯这么记：
- 分解（Divide）：把原问题拆成若干个规模更小的子问题
- 解决（Conquer）：递归地解决这些子问题。如果子问题足够小，就直接求解
- 合并（Combine）：把子问题的解合并成原问题的解
嗯，这里要注意：并不是所有问题都适合分治。只有那些「可以拆、拆完能合」的问题，才值得用分治。我在项目中见过不少强行用分治的代码，结果拆完合不回来，反而更复杂了。
分治算法的适用条件：
- 问题可以分解为结构相似的子问题
- 子问题的解可以合并为原问题的解
- 子问题之间相互独立（没有重叠）
二分搜索：最经典的分治
说到分治，二分搜索是绕不开的例子。它解决的问题很简单：在一个有序数组中找某个数。但它的思想，影响了无数算法设计。
二分搜索的思路是这样的：每次取中间元素，跟目标值比较。如果相等，直接返回；如果目标值小于中间元素，说明目标在左半部分；否则在右半部分。每次都能把搜索范围缩小一半。
我的经验：二分搜索看似简单，但边界条件特别容易写错。我曾经在一个嵌入式项目中，因为二分搜索的边界写成了 while (left < right) 而不是 while (left <= right)，导致数组越界，系统跑飞了。排查了整整一个下午才找到问题。
// 二分搜索的 C 语言实现
int binarySearch(int arr[], int left, int right, int target) {
while (left <= right) {
int mid = left + (right - left) / 2; // 防止溢出
if (arr[mid] == target) {
return mid; // 找到了
} else if (arr[mid] < target) {
left = mid + 1; // 目标在右半部分
} else {
right = mid - 1; // 目标在左半部分
}
}
return -1; // 没找到
}注意看 mid = left + (right - left) / 2 这个写法。为什么不用 (left + right) / 2？因为当 left 和 right 都很大时，left + right 可能会溢出。我在 32 位单片机上就踩过这个坑。
大整数乘法：化乘为加
大整数乘法是分治的另一个经典应用。你可能会问：乘法有什么好讲的？直接用 * 不就行了？
问题是，当整数大到几千位时，CPU 的乘法指令就无能为力了。我们需要自己实现乘法算法。传统的竖式乘法复杂度是 O(n²)，而用分治思想可以优化到 O(n^1.585)。
这个算法叫 Karatsuba 乘法，思路是这样的：
- 把两个 n 位数各拆成两半：高位和低位
- 计算三个乘积：高位乘高位、低位乘低位、以及 (高位+低位) 乘 (高位+低位)
- 通过加减组合得到最终结果
Karatsuba 公式：
设 X = a * 10^(n/2) + b, Y = c * 10^(n/2) + d
则 X * Y = ac * 10^n + (ad + bc) * 10^(n/2) + bd
其中 ad + bc = (a+b)(c+d) - ac - bd
你看，原本需要 4 次乘法，现在只需要 3 次。递归下去，复杂度就降低了。我在做密码学相关项目时，处理 RSA 的大数运算就用到了这个思想。
棋盘覆盖问题：视觉化的分治
棋盘覆盖问题是我个人觉得最有趣的分治例子。问题描述是这样的：
有一个 2^k × 2^k 的棋盘，其中恰好有一个方格是残缺的。现在要用 L 型骨牌（覆盖 3 个方格）覆盖整个棋盘，要求不重叠、不遗漏。
怎么解？分治！
把棋盘分成四个 2^(k-1) × 2^(k-1) 的小棋盘。残缺格在其中一个子棋盘里。我们在其他三个子棋盘的交界处放一个 L 型骨牌，这样每个子棋盘就都有一个「残缺格」了。然后递归处理每个子棋盘。
避坑指南：我曾经在实现棋盘覆盖时，递归的终止条件写错了。当棋盘大小为 1×1 时，应该直接返回，但我忘了处理，导致无限递归。调试时栈溢出，系统直接复位。从那以后，我写递归函数的第一件事就是先写终止条件。
// 棋盘覆盖的 C 语言框架
#define MAX_SIZE 1024
int board[MAX_SIZE][MAX_SIZE]; // 棋盘
int tile = 1; // 骨牌编号
void chessboard(int tr, int tc, int dr, int dc, int size) {
if (size == 1) return; // 终止条件
int s = size / 2;
int t = tile++;
// 覆盖左上角子棋盘
if (dr < tr + s && dc < tc + s) {
chessboard(tr, tc, dr, dc, s);
} else {
board[tr + s - 1][tc + s - 1] = t;
chessboard(tr, tc, tr + s - 1, tc + s - 1, s);
}
// 覆盖右上角子棋盘
if (dr < tr + s && dc >= tc + s) {
chessboard(tr, tc + s, dr, dc, s);
} else {
board[tr + s - 1][tc + s] = t;
chessboard(tr, tc + s, tr + s - 1, tc + s, s);
}
// 覆盖左下角子棋盘
if (dr >= tr + s && dc < tc + s) {
chessboard(tr + s, tc, dr, dc, s);
} else {
board[tr + s][tc + s - 1] = t;
chessboard(tr + s, tc, tr + s, tc + s - 1, s);
}
// 覆盖右下角子棋盘
if (dr >= tr + s && dc >= tc + s) {
chessboard(tr + s, tc + s, dr, dc, s);
} else {
board[tr + s][tc + s] = t;
chessboard(tr + s, tc + s, tr + s, tc + s, s);
}
}这段代码看起来有点长，但核心逻辑其实很简单：每次递归处理四个子棋盘，把「伪残缺格」放在交界处。递归深度是 k，所以对于 8×8 的棋盘，递归深度只有 3 层。
分治的时间复杂度分析
分治算法的时间复杂度，通常可以用主定理（Master Theorem）来分析。对于形如 T(n) = aT(n/b) + f(n) 的递归式：
| 条件 | 时间复杂度 | 典型例子 |
|---|---|---|
| f(n) = O(n^c) 且 c < log_b(a) | T(n) = Θ(n^log_b(a)) | 二分搜索：T(n) = T(n/2) + O(1) → Θ(log n) |
| f(n) = Θ(n^c) 且 c = log_b(a) | T(n) = Θ(n^c log n) | 归并排序：T(n) = 2T(n/2) + O(n) → Θ(n log n) |
| f(n) = Ω(n^c) 且 c > log_b(a) | T(n) = Θ(f(n)) | 棋盘覆盖：T(n) = 4T(n/2) + O(1) → Θ(n²) |
其实主定理不用死记硬背。你只要记住：分治的效率取决于「拆分的份数」和「合并的代价」之间的博弈。拆得越多，子问题越多；合并越复杂，总时间越长。
我的建议：在实际项目中，不要盲目追求理论上的最优分治。有时候递归带来的函数调用开销，反而比简单的 O(n²) 算法更慢。我在一个 ARM Cortex-M3 的嵌入式项目中，就遇到过递归深度过大导致栈溢出的问题。对于小规模数据，简单的循环往往更可靠。
分治算法的魅力在于，它把复杂问题变得有章可循。无论是二分搜索的简洁、大整数乘法的巧妙，还是棋盘覆盖的视觉美感，背后都是同一个思想：化整为零，逐个击破。掌握了这个思想，你会发现很多看似棘手的问题，其实都有迹可循。
公众号:蓝海资料掘金营，微信deep3321