19

为什么分而治之的算法通常比蛮力运行得更快？例如，查找最近的一对点。我知道你可以给我看数学证明。但直觉上，为什么会发生这种情况？魔法？

从理论上讲，“分而治之总是胜于蛮力”是真的吗？如果不是，有反例吗？

4

2 回答 2

26

对于您的第一个问题，分而治之背后的直觉是，在许多问题中，必须完成的工作量是基于输入的某些组合属性，而这些属性不是线性扩展的。

例如，在最近的点对问题中，蛮力答案的运行时间取决于您必须查看所有 O(n 2 ) 可能的点对的事实。

如果你把一个二次增长的东西切成两块，每块都是以前的一半大小，那么每一半解决问题需要初始时间的四分之一，所以解决两半问题大约需要时间蛮力解决方案所需时间的一半。把它切成四块需要四分之一的时间，把它切成八块需要八分之一的时间，以此类推。

在这种情况下，递归版本最终会更快，因为在每一步，我们通过确保没有太多我们实际需要检查的元素对来避免处理元素对的大量工作。由于类似的原因，大多数具有分而治之解决方案的算法最终会更快。

对于您的第二个问题，不，分而治之算法不一定比蛮力算法快。考虑在数组中找到最大值的问题。蛮力算法需要 O(n) 时间并使用 O(1) 空间，因为它对数据进行线性扫描。这里给出了分而治之的算法：

  • 如果数组只有一个元素，那就是最大值。
  • 否则：
    • 将阵列切成两半。
    • 找出每一半的最大值。
    • 计算这两个值的最大值。

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

再举一个例子，最大单笔销售利润问题有一个分而治之的解决方案，但优化的动态规划解决方案在时间和内存上都更快。

希望这可以帮助！

于 2012-06-15T00:50:14.660 回答
5

我建议你通读算法设计的第 5 章，它很好地解释了分治法。

直观地说，对于一个问题，如果你能把它分成两个与源问题相同模式的子问题，并且将两个子问题的结果合并成最终结果的时间复杂度有点小，那就更快了而不是通过蛮力解决原始的完整问题。

正如Algorithm Design中所说，实际上你不能从分治法中获得太多时间，一般来说，你只能将时间复杂度从较高的多项式降低到较低的多项式（例如从 O(n^3) 到 O(n^ 2))，但几乎没有从指数到多项式（例如从 O(2^n) 到 O(n^3)）。

我认为你能从分而治之中获得的最大收获是解决问题的心态。将最初的大问题分解为更小、更容易的子问题总是一个很好的尝试。即使你没有得到更好的运行时间，它仍然可以帮助你思考问题。

于 2012-06-15T00:58:54.423 回答