以N的方式合并时间复杂度 [英] Time complexity using N way Merge

问题描述

我会在2路合并排序算法，如果我们可以得到在时间上更好的收益想通过降低合并通行证。

I was going over the 2 way merge sort algorithm and was thinking if by reducing the merge passes can we get better gain in terms of time.

如在2路合并，我们有以下的复发：

E.g in a 2 way merge we have the following recurrence:

T（N）= 2T（N / 2）+ O（N）

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

和这个有N.log-BASE2（N）的时间复杂度

and this has a time complexity of N.log-base2(N)

如果我把这个问题由4和合并4子阵列我会得到

if I divide the problem by 4 and merge 4 sub arrays I will get

T（N）= 4T（N / 4）+ O（N）

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

这应该有N.log-base4的时间复杂度（N）

and this should have a time complexity of N.log-base4(N)

一直以来，合并的遍数减少了，这应该是一些实施归并排序时要考虑的？

Since, the number of merge passes has reduced, should this be something to consider when implementing merge sort ?

例如，使用的64个元素的第一种方法的数组将有6张通行证，并使用第二种方法将有3次通过。

e.g with an array of 64 elements the first approach will have 6 passes and using the second approach it will have 3 passes.

编辑：

好了，有2T（N / 2），我们正在做的比较ň每次传球和4T（N / 4），我们最终做每道3 * N的比较？什么运动部件造成arrary的成本，这是否保持同样的在每遍？

Ok, so with 2T(n/2) we are doing N comparisons per pass and with 4T(n/4) we end up doing 3*N comparisons per pass ? What about the cost of moving elements to result arrary, does that remain same at each pass ?

推荐答案

需要注意的是基4日志的数量是完全一半的基2日志的数量;因此，你只引进一个常数因子加速。除非你不是，因为你在实际的合并成本推出类似的常数因子SLOWDOWN（2路合并需要每件1相比，4路，可能需要最多3个）。因此，尽管可能会减少，通行证，通行证各自更昂贵。所以，你复杂的codeA公平一点，而利益是有问题。

Note that the base-4 log of a number is exactly half the base-2 log of a number; thus, you're only introducing a constant-factor speedup. Except you're not, because you introduce a similar constant-factor SLOWDOWN in the cost of the actual merging (2-way merge needs 1 comparison per item, 4-way may need up to 3). So while there may be fewer passes, the passes are each more costly. So you've complicated the code a fair bit, and the benefits are in question.

这篇关于以N的方式合并时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！