12.1 分治算法¶
分治(divide and conquer),全称分而治之,是一种非常重要且常见的算法策略。分治通常基于递归实现,包括“分”和“治”两个步骤。
- 分(划分阶段):递归地将原问题分解为两个或多个子问题,直至到达最小子问题时终止。
- 治(合并阶段):从已知解的最小子问题开始,从底至顶地将子问题的解进行合并,从而构建出原问题的解。
如图 12-1 所示,“归并排序”是分治策略的典型应用之一。
- 分:递归地将原数组(原问题)划分为两个子数组(子问题),直到子数组只剩一个元素(最小子问题)。
- 治:从底至顶地将有序的子数组(子问题的解)进行合并,从而得到有序的原数组(原问题的解)。
图 12-1 归并排序的分治策略
图解 12-1:用归并排序理解“分”与“治”
将八元素排序问题逐层分解至单元素最小子问题,再自底向上合并有序结果,得到 0 至 7 的升序数组。
输入数组为 [7, 3, 2, 6, 0, 1, 5, 4],画面上半部分为“分(划分阶段)”,下半部分为“治(合并阶段)”。
不断把当前数组对半划分,直到每个子问题只含一个元素。左右两部分互不重叠,可各自求解;单元素无需比较就是有序结果。
返回时将相邻的两个有序结果合并。每次比较两边首个尚未取出的元素,取较小者;一边取完后接上另一边的剩余元素。逐层合并后解决完整八元素问题。
图的上半部分经三层划分到达八个单元素,下半部分经三层合并得到有序结果;下表按画面层级列出全部七层子数组。
| 阶段 | 每个子数组长度 | 子数组(按原左右位置) |
|---|---|---|
| 原问题 | 8 | [7,3,2,6,0,1,5,4] |
| 划分为两个子问题 | 4 | [7,3,2,6];[0,1,5,4] |
| 继续划分 | 2 | [7,3];[2,6];[0,1];[5,4] |
| 最小子问题 | 1 | [7];[3];[2];[6];[0];[1];[5];[4] |
| 合并为四个有序结果 | 2 | [3,7];[2,6];[0,1];[4,5] |
| 合并为两个有序结果 | 4 | [2,3,6,7];[0,1,4,5] |
| 合并为原问题的解 | 8 | [0,1,2,3,4,5,6,7] |
由于子问题与原问题同属数组排序、左右子数组相互独立,且两个有序子数组可以高效合并为一个有序数组,这体现了分治问题可分解、子问题独立、解可合并的特点。
12.1.1 如何判断分治问题¶
一个问题是否适合使用分治解决,通常可以参考以下几个判断依据。
- 问题可以分解:原问题可以分解成规模更小、类似的子问题,以及能够以相同方式递归地进行划分。
- 子问题是独立的:子问题之间没有重叠,互不依赖,可以独立解决。
- 子问题的解可以合并:原问题的解通过合并子问题的解得来。
显然,归并排序满足以上三个判断依据。
- 问题可以分解:递归地将数组(原问题)划分为两个子数组(子问题)。
- 子问题是独立的:每个子数组都可以独立地进行排序(子问题可以独立进行求解)。
- 子问题的解可以合并:两个有序子数组(子问题的解)可以合并为一个有序数组(原问题的解)。
12.1.2 通过分治提升效率¶
分治不仅可以有效地解决算法问题,往往还可以提升算法效率。在排序算法中,快速排序、归并排序、堆排序相较于选择、冒泡、插入排序更快,就是因为它们应用了分治策略。
那么,我们不禁发问:为什么分治可以提升算法效率,其底层逻辑是什么?换句话说,将大问题分解为多个子问题、解决子问题、将子问题的解合并为原问题的解,这几步的效率为什么比直接解决原问题的效率更高?这个问题可以从操作数量和并行计算两方面来讨论。
1. 操作数量优化¶
以“冒泡排序”为例,其处理一个长度为 \(n\) 的数组需要 \(O(n^2)\) 时间。假设我们按照图 12-2 所示的方式,将数组从中点处分为两个子数组,则划分需要 \(O(n)\) 时间,排序每个子数组需要 \(O((n / 2)^2)\) 时间,合并两个子数组需要 \(O(n)\) 时间,总体时间复杂度为:
图 12-2 划分数组前后的冒泡排序
图解 12-2:把一次冒泡排序拆成两个较小排序任务
对比直接冒泡排序八个元素与先二分再分别冒泡排序后合并,二者结果相同,且单次划分后仍为平方阶。
左右两条对比路线的共同输入为 [7, 3, 2, 6, 0, 1, 5, 4],共同排序目标为 [0, 1, 2, 3, 4, 5, 6, 7]。设数组长度为 n,本图通过复杂度表达式对比划分前后的操作量构成,并未提供实测耗时数据。
左侧路线直接对长度为 n 的完整数组执行冒泡排序,标注时间开销为 O(n²),底部输出升序数组 [0, 1, 2, 3, 4, 5, 6, 7]。
右侧路线先将原数组从中点划分为左半 [7, 3, 2, 6] 和右半 [0, 1, 5, 4],图中标注“划分 O(n)”;随后对两个长度为 n/2 的子数组分别执行冒泡排序,各自标注“冒泡排序 O((n/2)²)”,得到有序左半 [2, 3, 6, 7] 与有序右半 [0, 1, 4, 5];最后执行“合并 O(n)”,交错取出两侧较小元素合成 [0, 1, 2, 3, 4, 5, 6, 7]。
右侧合并阶段的交叉箭头表明两个有序半区的元素需按大小穿插归并,而非简单前后拼接。画面底部将右侧总复杂度汇总为“总体 O(n²/2 + 2n)”,对应两次半规模冒泡排序加上线性划分与合并。
单次划分后的 O(n²/2 + 2n) 在渐近意义下仍为 O(n²)。图中的简化表达式展示平方项系数减小的可能收益,不是精确操作次数,也不能保证实际耗时减半。
接下来,我们计算以下不等式,其左边和右边分别为划分前和划分后的操作总数:
这意味着当 \(n > 4\) 时,划分后的操作数量更少,排序效率应该更高。请注意,划分后的时间复杂度仍然是平方阶 \(O(n^2)\) ,只是复杂度中的常数项变小了。
进一步想,如果我们把子数组不断地再从中点处划分为两个子数组,直至子数组只剩一个元素时停止划分呢?这种思路实际上就是“归并排序”,时间复杂度为 \(O(n \log n)\) 。
再思考,如果我们多设置几个划分点,将原数组平均划分为 \(k\) 个子数组呢?这种情况与“桶排序”非常类似,它非常适合排序海量数据,理论上时间复杂度可以达到 \(O(n + k)\) 。
2. 并行计算优化¶
我们知道,分治生成的子问题是相互独立的,因此通常可以并行解决。也就是说,分治不仅可以降低算法的时间复杂度,还有利于操作系统的并行优化。
并行优化在多核或多处理器的环境中尤其有效,因为系统可以同时处理多个子问题,更加充分地利用计算资源,从而显著减少总体的运行时间。
比如在图 12-3 所示的“桶排序”中,我们将海量的数据平均分配到各个桶中,则可将所有桶的排序任务分散到各个计算单元,完成后再合并结果。
图 12-3 桶排序的并行计算
图解 12-3:桶排序的并行计算结构
将无序数据分配到六个桶中,交由六个计算单元并行排序,再按序汇集为有序数据。
这是一张展示分治并行化的结构示意图,未指定具体数组元素、桶边界数值或运行耗时。画面自上而下依次排列顶部的“无序数据”、中间的六个“桶”与六个“计算单元”,以及底部的“有序数据”。
顶部的无序数据沿六条向下分支箭头分配到六个桶中;每个桶各通过一条竖直虚线对应下方的计算单元,表示六个桶的内部排序任务彼此独立、互不依赖,可分发给不同计算单元同时并行处理。
六个计算单元完成各自桶内排序后,输出箭头汇总到底部的有序数据。在按数值范围有序划分的桶排序中,各计算单元排好本桶数据后,还需按桶的范围先后顺序依次收集,才能拼出全局有序结果。
本图旨在说明分治产生的独立子问题有利于多核或多处理器并行加速,并未展示各桶的数据量分布或通信合并开销,因此不能由图中画出六个计算单元直接推断运行速度必定提升六倍。
分治策略将原排序问题拆解为互不重叠的多个桶内排序子问题,使多个计算单元得以并行执行,最后再合并各子问题的解。
12.1.3 分治常见应用¶
一方面,分治可以用来解决许多经典算法问题。
- 寻找最近点对:该算法首先将点集分成两部分,然后分别找出两部分中的最近点对,最后找出跨越两部分的最近点对。
- 大整数乘法:例如 Karatsuba 算法,它将大整数乘法分解为几个较小的整数的乘法和加法。
- 矩阵乘法:例如 Strassen 算法,它将大矩阵乘法分解为多个小矩阵的乘法和加法。
- 汉诺塔问题:汉诺塔问题可以通过递归解决,这是典型的分治策略应用。
- 求解逆序对:在一个序列中,如果前面的数字大于后面的数字,那么这两个数字构成一个逆序对。求解逆序对问题可以利用分治的思想,借助归并排序进行求解。
另一方面,分治在算法和数据结构的设计中应用得非常广泛。
- 二分查找:二分查找是将有序数组从中点索引处分为两部分,然后根据目标值与中间元素值比较结果,决定排除哪一半区间,并在剩余区间执行相同的二分操作。
- 归并排序:本节开头已介绍,不再赘述。
- 快速排序:快速排序是选取一个基准值,然后把数组分为两个子数组,一个子数组的元素比基准值小,另一子数组的元素比基准值大,再对这两部分进行相同的划分操作,直至子数组只剩下一个元素。
- 桶排序:桶排序的基本思想是将数据分散到多个桶,然后对每个桶内的元素进行排序,最后将各个桶的元素依次取出,从而得到一个有序数组。
- 树:例如二叉搜索树、AVL 树、红黑树、B 树、B+ 树等,它们的查找、插入和删除等操作都可以视为分治策略的应用。
- 堆:堆是一种特殊的完全二叉树,其各种操作,如插入、删除和堆化,实际上都隐含了分治的思想。
- 哈希表:虽然哈希表并不直接应用分治,但某些哈希冲突解决方案间接应用了分治策略,例如,链式地址中的长链表会被转化为红黑树,以提升查询效率。
可以看出,分治是一种“润物细无声”的算法思想,隐含在各种算法与数据结构之中。