algorithm - 为什么分而治之算法通常比蛮力法运行得更快？

Question

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

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

Answer 1

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

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

如果你把一个二次方增长的东西切成两 block ，每 block 都是原来的一半大小，那么每一半都需要初始时间的四分之一来解决这个问题，所以在两半都解决这个问题花费的时间大约是蛮力解决方案所需时间的一半。将它切成四 block 需要四分之一的时间，将它切成八 block 需要八分之一的时间，等等。

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

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

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

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

再举一个例子，maximum single-sell profit problem具有分而治之的解决方案，但优化的动态规划解决方案在时间和内存上都更快。

希望这对您有所帮助!