已读93%
预计阅读本页时间：-
预计阅读本页时间：-
原则：将问题分解至更小的问题
在设计一个高效算法来解决问题时，能将问题分解成两个（甚至更多）更小的子问题是非常有帮助的。快速排序毫无疑问是最流行的排序算法之一。尽管通过精心构造的特殊情况会引发性能问题，快速排序还是做到在大数据集上平均性能最高。事实上，在O(n log n)的算法之中，都包含分解问题的思想，首先将一个大小为n的问题分解为两个n/2的子问题，然后再将两个子问题的结果汇总，作为原问题的结果。要达到O(n log n)的复杂度，这两个步骤都需要达到O(n)的复杂度才行。
快速排序是第一个能够达到O(n log n)性能的原地置换排序算法。它的成功之处就在于将问题分成两个部分，并递归地通过快速排序来解决更小的子问题（几乎与直觉恰恰相反）。
这种新方法仅仅简单地将问题一分为二，就能够带来令人惊异的性能提升。看看二分查找如何将一个大小为n的问题转换为两个大小为n/2的问题。二分查找借助于查找问题的重复特性来递归地解决问题。
广告：个人专属 VPN，独立 IP，无限流量，多机房切换，还可以屏蔽广告和恶意软件，每月最低仅 5 美元
有时候通过分解为两个子问题来解决问题时可以不使用递归。比如凸包扫描就将两个上凸包和下凸包合并来构建最终的凸包。
有时，一个问题在相同的输入数据下可以被分解为不同的（看似无关的）子问题。Ford-Fulkerson算法通过反复搜索可以增加流的增广路来计算网络流中的最大流，一旦找不到增广路，问题的求解就完成了。插入排序反复查找数组中的最大值，并将其置换到数组的最右端，经过n次计算，数组便有序了。相似地，堆排序也是反复将堆中最大的元素置换到适当的位置上。
表11-2比较了第5章讨论过的查找算法。
