分而治之 - 它为什么起作用？

Question

我知道，像归并排序和快速排序算法使用分而治之的模式，但我不知道为什么它在降低了时间复杂度工作...

为什么通常不会是“分而治之”的算法工作比非分而治之更好？

Answer 1

分而治之作品，因为数学支持它！

考虑这几个分治法：

1）二进制搜索：该算法降低了你的输入空间各占一半时间。直观地表明这比线性搜索更好，因为我们会避免查看很多元素。

但是有多好？我们得到的复发率（注：这是复发的最坏情况分析）：

T(n) = T(n/2) + O(1)

数学意味着T(n) = Theta(log n)。因此这比线性搜索指数地更好。

2）合并排序：在这里我们分成两个（几乎）相等的一半，排序一半，然后合并它们。为什么这应该比二次方好？这是复发：

T(n) = 2T(n/2) + O(n)

可以从数学上（说使用主定理），其T(n) = Theta(n log n)。因此T（n）渐近地好于二次方。

观察该天真快速排序结束了给我们最坏的情况下复发的

T(n) = T(n-1) + O(n)

其中数学，出来是二次，并在最坏的情况下，也不好过冒泡排序（渐近地说）。但是，我们可以证明，在一般情况下，快速排序是O（n log n）。

3选择算法：这是一个征服算法来寻找第k个最大的元素。这种算法是否优于排序（或者甚至不是二次的）并不明显。

但在数学上，其复发（再次最坏情况）出来是

T(n) = T(n/5) + T(7n/10 + 6) + O(n)

可以证明数学是T(n) = O(n)，因此它比分拣好。

也许一个共同的方式来看待他们：

你可以看一下算法，树，其中每个子问题成为当前的一个子树和节点可以用的工作量进行标记完成，然后可以为每个节点添加全部工作。

对于二分查找，工作是O（1）（只是一个比较）和其中一个子树，工作是0，所以工作的总量是O（log n）（本质上是一个路径，就像我们在二叉搜索树中做的那样）。

对于合并排序，对于有k个孩子的节点，工作是O（k）（合并步骤）。在每个级别完成的工作是O（n）（n，n/2 + n/2，n/4 + n/4 + n/4 + n/4等），并且有O（log n）级别，所以合并排序是O（n log n）。

对于快速排序，在最坏的情况下，二叉树实际上是一个链表，因此完成的工作是n + n-1 + ... + 1 = Omega（n^2）。

对于选择排序，我不知道如何可视化它，但我相信把它看作一个有3个孩子（n/5,7n/10和其余）的树可能仍然有帮助。

Answer 2

分而治之的算法不“通常更好”。正如其他非分而治之算法一样，它们只是起作用。它们不会降低排序的复杂性，它们和其他算法一样好。

Answer 3

分而治之算法的工作速度更快，因为他们最终只做更少的工作。

考虑二进制搜索的经典分而治之算法：与其查看N项目以查找答案，二分搜索最终仅检查其中的Log2N。当然，当你做更少的工作时，你可以更快地完成;这正是分而治之算法的发展方向。

当然，结果很大程度上取决于你的策略在分工方面的表现如何：如果分部在每一步中或多或少都公平（即将工作划分为一半），则可以获得完美的速度。但是，如果分割并不完美（例如最坏的快速排序情况，当它将O(n^2)排序为数组，因为它在每次迭代中只消除了一个元素），那么分治策略并没有什么帮助，因为您的算法不会不减少工作量。

Answer 4

因为在某些情况下，最好将问题分成较小的子问题，这比原始问题要容易得多。即使增加了合并（合并）部分解决方案的复杂性。

我认为现实世界与战争类比（消除敌人）是准确的。分开你的敌人，分开摧毁它们，比同时处理它们更好。

而且作为alestanis已经说过，分治算法只是一类算法，并不能保证它比不分割和征服要快。例如，堆排序与合并排序具有相同的渐近复杂性。另一方面，Quicksort的复杂程度比他们两个都差，但平均表现更好....