algorithm - 分而治之——为什么有效？

Question

我知道像mergesort和quicksort这样的算法使用分而治之的范式，但我想知道为什么它可以降低时间复杂度......

为什么通常“分而治之”的算法比非分而治之的算法效果更好？

Answer 1

分而治之的算法工作得更快，因为它们最终做的工作更少。

考虑一下二分搜索的经典分治算法：二分搜索不是通过查看N项目来找到答案，而是最终只检查Log2N它们。自然，当你做的工作越少，你就能完成得越快；这正是分治算法正在发生的事情。

当然，结果很大程度上取决于您的策略在划分工作方面的效果：如果划分在每一步都或多或少公平（即您将工作分成两半），那么您将获得完美的Log2N速度。但是，如果划分不完美（例如快速排序的最坏情况，当它花费O(n^2)对数组进行排序时，因为它在每次迭代中只消除了一个元素），那么分而治之的策略就没有帮助，因为您的算法没有减少工作量。

Answer 2

分而治之的算法不会“通常工作得更好”。它们只是工作，就像其他非分而治之的算法一样。它们不会降低排序复杂性，它们与其他算法一样好。

Answer 3

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

考虑一些分而治之的算法：

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)，因此它比排序更好。

也许是一种常见的看待它们的方式：

您可以将算法视为树，其中每个子问题都成为当前的子树，并且可以用完成的工作量标记节点，然后可以为每个节点添加总工作量。

对于二分查找，work是O(1)（只是比较），其中一个子树，work是0，所以总的work是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 和其余）的树可能仍然有帮助。