15 algorithm complexity-theory brute-force divide-and-conquer
为什么分而治之的算法通常比蛮力运行得更快？例如,找到最接近的一对点.我知道你可以告诉我数学证明.但直觉上,为什么会这样呢？魔法？
从理论上说,"分而治之总是比蛮力更好"吗？如果不是,是否有任何反例？
tem*_*def 21
对于你的第一个问题,分而治之后的直觉是,在许多问题中,必须完成的工作量是基于输入的一些组合属性,这些属性比线性扩展更多.
例如,在最接近的点对问题中,蛮力答案的运行时间取决于您必须查看所有O(n 2)个可能的点对.
如果你采取一些平方增长的东西并将其切成两块,每块都是以前的一半,那么每半年需要四分之一的时间来解决问题,所以解决这两个问题大致需要时间蛮力解决方案所需时间的一半.把它切成四块,需要四分之一的时间,一次八分之一就把它切成八块,等等.
在这种情况下,递归版本最终变得更快,因为在每一步中,我们都避免通过确保实际上不需要检查的对太多来处理元素对而做很多工作.由于类似的原因,大多数具有分而治之解决方案的算法最终都会更快.
对于你的第二个问题,不,分而治之的算法不一定比蛮力算法更快.考虑在数组中找到最大值的问题.蛮力算法需要O(n)时间并使用O(1)空间,因为它对数据进行线性扫描.这里给出了分而治之的算法:
这也需要时间O(n),但是使用O(log n)内存作为堆栈空间.它实际上比简单的线性算法更糟糕.
另一个例子是,最大的单一销售利润问题有一个分而治之的解决方案,但优化的动态编程解决方案在时间和内存上都更快.
希望这可以帮助!
我建议你通读算法设计的第 5 章，它很好地解释了分而治之。
直观上，对于一个问题，如果你能把它分成两个子问题，模式与原问题相同，并且将两个子问题的结果合并成最终结果的时间复杂度有点小，那么它会更快而不是用蛮力解决原始的完整问题。
正如算法设计中所说，实际上你不能从分治中获得太多时间，一般你只能将时间复杂度从较高的多项式降低到较低的多项式（例如从 O(n^3) 到 O(n^) 2))，但很难从指数到多项式（例如从 O(2^n) 到 O(n^3)）。
我认为你从分而治之中获得的最大好处是解决问题的心态。将最初的大问题分解为更小、更容易的子问题总是一个很好的尝试。即使您没有获得更好的运行时间，它仍然可以帮助您思考问题。