为什么分治算法通常比暴力算法运行更快？

Question

为什么分治算法经常比暴力算法运行更快？例如，要查找最近的点对。我知道你可以向我展示数学证明。但直觉上，为什么会发生这种情况？魔法吗？

从理论上讲，“分而治之总是比暴力求解更好”这种说法是否正确？如果不是，是否存在反例？

- user1445654

---

将一个蛋糕分成16份的第一种方法是尝试切割1/16的蛋糕，这很困难。另一种方法是先将蛋糕切成2块，再将每一块切成2块，然后将每个1/4切成2块，最后将每个1/8切成2块即可。 - Déjà vu

Answer 1

对于您的第一个问题，分治算法背后的直觉是，在许多问题中，必须要处理的工作量基于输入的某种组合属性，并且具有大于线性的规模。

例如，在最近点对问题中，暴力答案的运行时间取决于您必须查看所有O(n²)个点对。

如果将二次增长的东西分成两部分，每个部分的大小都是之前的一半，则解决每个部分的问题需要花费初始时间的四分之一，因此在两个部分中解决问题需要的时间大约是蛮力解决方案所需时间的一半。将其分为四个部分需要四分之一的时间，将其分成八个部分需要八分之一的时间，以此类推。

在这种情况下，递归版本最终更快，因为在每个步骤中，通过确保不需要检查太多实际上需要检查的元素对，可以避免处理元素对所需的大量工作。大多数具有分治解决方案的算法出于类似的原因而更快。

对于您的第二个问题，分治算法不一定比暴力算法更快。考虑查找数组中的最大值问题。暴力算法需要O(n)时间，并使用O(1)空间，因为它对数据进行线性扫描。以下是分治算法：

• 如果数组只有一个元素，则它就是最大值。
• 否则：
  • 将数组分成两半。
  • 在每个半部分找到最大值。
  • 计算这两个值的最大值。

这也需要O(n)时间，但是使用O(log n)内存作为堆栈空间。实际上比简单的线性算法更糟糕。

作为另一个例子，最大单卖利润问题具有分治解决方案，但优化的动态规划解决方案在时间和内存方面都更快。

希望这会有所帮助！

- templatetypedef

Answer 2

我建议您阅读《算法设计》第5章，它很好地解释了分治算法。

直观地说，对于一个问题，如果您可以将其分成两个具有与原始问题相同模式的子问题，并且合并两个子问题的结果以得到最终结果的时间复杂度较小，则比通过暴力方法解决原始完整问题更快。

正如《算法设计》所述，从时间角度来看，您实际上无法从分治算法中获得太多收益，通常只能将时间复杂度从高多项式降低到低多项式（例如从O(n^3)降低到O(n^2)），但几乎不可能从指数级别降低到多项式级别（例如从O(2^n)降低到O(n^3)）。

我认为您从分治算法中最大的收益是解决问题的思维方式。将原始大问题拆分成更小、更简单的子问题总是一个不错的尝试。即使您没有获得更好的运行时间，这仍然有助于您深入思考问题。

- xvatar