使用N路合并的时间复杂度

Question

使用N路合并的时间复杂度

4

我正在研究双向归并排序算法，思考通过减少合并次数是否能够在时间上获得更好的收益。例如，在2路归并中，我们有以下递归式：T(n) = 2T(n/2) + O(n)，其时间复杂度为N.log-base2(N)。如果我将问题分成4个部分并合并4个子数组，则会得到 T(n) = 4T(n/4) + O(n)，这应该具有时间复杂度 N.log-base4(N)。由于合并次数减少了，因此在实现归并排序时应该考虑这一点。例如，对于一个包含64个元素的数组，第一种方法将需要6次合并，而使用第二种方法只需要3次合并。编辑：好的，所以在2T(n/2)中，每次合并需要进行N次比较，在4T(n/4)中，每次合并需要进行3*N次比较？移动元素到结果数组的成本是否在每次合并时保持不变？

- Frank Q.

3个回答

0

听起来很合理，但事实并非如此，因为在这种情况下，您必须至少进行5次比较以对每4个元素进行排序。这样，您将有5*N*log4(N)次比较，而这比N*log2(N)多了一个因子5*log(2)/log(4)。

- Luka Rahne

1

假设其中3个元素已经排序好了，我认为加入第4个元素不需要5次比较。 - Scott Hunter

如果你将新人与三个排序中的中间值进行比较，就可以避免与最大值或最小值进行比较，因此只需要两次比较。 - Scott Hunter

排序最多需要4个元素，需要4次比较。 - Saeed Amiri

应该是这样的：从排序后的列表1中选取第一个元素并与剩下3个排序后的列表的第一个元素进行比较，重复N次即可得到3.N个结果。 - Frank Q.

0

分解树的高度为log₄n，但运行时间不是n log₄n。

第一步中，您有四个大小为n/4的列表，它们的合并需要n/4 + n/4 + n/2次比较。但在正常情况下，它只需要n/2次比较，因此您可以将树的高度减半，但每个合并都要乘以二，因此总运行时间不比分成两部分更好。（您可以证明对于树的其他深度，您应该至少比具有两个分支的树多进行两倍的比较。）

附言：运行时间指比较次数。

- Saeed Amiri

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Scott Hunter · Accepted Answer

注意，一个数的以4为底的对数恰好是以2为底的对数的一半；因此，你只是引入了一个常数加速。但实际上你没有，因为在合并的成本中引入了类似的恶化常数（2路合并每个项目需要1个比较，4路合并可能需要3个）。因此，虽然可能会有更少的传递，但每个传递的成本都更高。所以你已经使代码变得相当复杂，而且收益也值得怀疑。