合并排序的数组，什么是最佳的时间复杂度？ [英] Merging sorted arrays, what is the optimum time complexity?

问题描述

我有m个阵列，每个阵列是长度为n的。每个数组排序。我想创建长度为m * n的单个阵列，含有该previous阵列（包括重复的值），来分类的所有的值。我必须合并这些阵列。

I have m arrays, every array is of length n. Each array is sorted. I want to create a single array of length m*n, containing all the values of the previous arrays (including repeating values), sorted. I have to merge these arrays..

我觉得最佳的时间复杂度为M * N *日志（M）

I think the optimum time complexity is m*n*log(m)

下面是该算法的草图。

我创建lenth米的支撑排列H，包含每个数组的第一个元素的所有值。

I create a support array H of lenth m, containing all the values of the first element of each array.

我再排序数组（M数米），和最小值移动到输出数组。

I then sort this array (m log m), and move the min value to the output array.

我再更换移动值与下一个，从阵列中它被采取。其实我并没有取代它，但我在正确的（排序）位置插入。这取log M的，我认为。

I then replace the moved value with the next one, from the array it was taken. Actually I don't replace it, but I insert it in the right (sorted) position. This take log m I think.

和我重复这对所有的m * n的值。所以M * N * log M的

And I repeat this for all m*n values... therefore m*n*log m

我的问题......你能想到一个更有效的算法吗？如果mnlogm实际上是最佳的，可你至少觉得一个更简单，更优雅的算法研究的？

My question.. can you think of a more efficient algorithm? If mnlogm is actually optimum, can you at least think of a simpler, more elegant algorith?

推荐答案

的复杂性是正确的！然而，有一个小瑕疵你的算法的想法：在 log M的您不能插入一个排序的数组中的项目。您可以使用这种复杂的二进制搜索找到自己的位置，但你可能需要左右移动的元素实际上将它放在这里。要解决这个问题，你可以使用一个堆数据结构，而不是！

The complexity is right! However, there's a small flaw in your algorithm idea: You cannot insert an item in a sorted array in log m. You can find its position using binary search in that complexity, but you might have to move elements around to actually place it there. To fix this problem, you can use a heap data-structure instead!

多路合并（这是你的算法的通用名称）通常又一个融合的数据结构来实现：比赛树。你可以找到Knuth的艺术计算机编程的描述（章排序，IIRC）。相比，在这种特殊情况下堆它在理论和实践较低的常数因子。

Multi-way merge (which is the common name of your algorithm) is usually implemented with yet another 'merging' data-structure: the tournament-tree. You can find a description in Knuth's "The Art of Computer Programming" (Chapter on Sorting, iirc). It has a lower constant factor in theory and in practice when compared to heaps in this specific case.

如果你想看看实现，我pretty的确认并行多路合并在GNU C ++标准库的并行扩展是实现这种方式。

If you want to look implementations, I'm pretty sure that the parallel multi-way merge in the GNU C++ Standard library parallel-extensions is implemented this way.

编辑：我引用错了书，现在是固定的。

I referenced the wrong book, which is fixed now.

这篇关于合并排序的数组，什么是最佳的时间复杂度？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！