分治
复习
- 排序问题与稳定性：稳定性的含义
- 冒泡排序与选择排序：两种
O(n²)的简单排序 - 插入排序：插入排序像整理扑克牌，把新牌插入已排好的部分
TL;DR
- 分治把问题拆成若干更小的同类子问题
- 分别解决后，再把结果合并起来
- 它天然对应递归
- 归并排序、快速排序都建立在分治之上
正文
前面几章的排序都是“一锅端”，最多到 O(n²)。要更快，需要换一种思路。这个思路叫分治（divide and conquer），核心只有三个字：分、治、合。
分、治、合
分治把一个大问题，按这三步处理：
- 分：把问题拆成若干个规模更小的同类子问题
- 治：递归地解决这些子问题（小到可以直接处理时，就直接处理）
- 合：把子问题的结果合并成原问题的答案
你会发现，这和前面讲的“设计递归”几乎是一回事：分治就是递归思想在“把问题拆开”这件事上的具体运用。 因为子问题还是同类问题，所以递归写起来非常自然。
其实二分查找也是分治的一个例子：把查找范围一分为二，只在其中一半继续找。
为什么它有用
分治之所以有效，靠的是两点：
- 子问题规模缩小：规模一大，代价增长很快；拆小之后，处理每个子问题都更便宜
- 子问题可以独立解决：互不干扰，便于分别处理，也便于并行
但分治并非没有成本。“分”和“合”本身都要花时间，尤其是“合”这一步。如果合并的代价比节省的还大，分治就不划算了。所以，分治能不能真正提速，关键看拆分和合并的设计。
拿排序来说，如果只是把数组分成两半分别排好，但合并不好，那也没用。可如果能做到“线性时间合并两个有序序列”，就能得到一个漂亮的 O(n log n) 排序——这就是下一章的归并排序。
思考题 1
分治的三个步骤分别是什么？
思考题 2
分治为什么天然适合用递归实现？
小结
知识点
- 分治分三步：分、治、合
- 子问题与原问题同类，因此适合递归
- 子问题规模缩小且相互独立
- 分治效果取决于拆分与合并的设计
参考资料
- Wikipedia(zh)：分治法：把问题分解、求解再合并的策略
- Wikipedia(zh)：算法设计：常见算法设计范式
思考题答案（仅供参考）
思考题 1
分：把问题拆成若干更小的同类子问题；治：递归地解决这些子问题；合：把子问题的结果合并成原问题的答案。
思考题 2
因为分治拆出的子问题与原问题“同类、但规模更小”，这正符合递归的适用条件：可以递归地调用同一个解法去处理子问题，递归到可以直接求解的最小规模为止。因此分治通常用递归表达最自然。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪