合并排序数组，最优时间复杂度是什么？

Question

合并排序数组，最优时间复杂度是什么？

arraysalgorithmsortingdata-structurescomplexity-theory

6

我有m个长度为n的数组，每个数组都是排序的。我想创建一个长度为m*n的单个数组，其中包含先前数组的所有值（包括重复值），并进行排序。我必须合并这些数组。

我认为最优的时间复杂度是m*n*log（m）。

以下是算法的概述。

我创建了一个支持数组H，其长度为m，包含每个数组的第一个元素的所有值。

然后，我对此数组进行排序（m log m），并将最小值移动到输出数组中。

然后，我用从它被取出的数组中的下一个值替换已移动的值。实际上，我不会替换它，而是将其插入正确（排序）的位置。我认为这需要log m。

我为所有m*n个值重复此操作...因此m*n*log m

我的问题是：您能否想到更有效的算法？如果mnlogm实际上是最优的，您至少可以想到一个更简单，更优雅的算法吗？

- francesco delvinis

3

在一个已排序的数组中插入一个元素如何能够在对数时间内完成？ - codaddict

2个回答

0

你能做到的最好的是O(m*n + d)。类似于计数排序：http://en.wikipedia.org/wiki/Counting_sort 如果你知道可能的值范围（比如d），你可以初始化一个长度为d的数组，然后扫描每个m个数组，在对应的bin中的每个值上加1。然后在你的新数组中，对于d中的每个值，你都要添加该bin有多少个计数。

- TimCodes.NET

正如你所写的，这仅在您知道“d”并且存在从您的值空间到整数的_easy_映射时才起作用。此外，内存复杂度是线性的'd'，如果您具有大的值范围，则可能很糟糕。因此，这不一定更好。 - ltjax

是的，我想这取决于他的数据集。 - TimCodes.NET

在执行挂起的LRU操作之前，我会在ConcurrentLinkedHashMap中执行此操作，以便它们按严格顺序执行。如果出现冲突，例如闭合地址，我会进行链接。我认为这种方法被称为有界高度优先队列。 - Ben Manes

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

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

- ltjax · Accepted Answer

算法本身的复杂度没问题！然而，你的算法有一个小缺陷：在已排序的数组中无法以 log m 的时间插入一个项。虽然你可以使用二分查找来找到其位置，但实际上可能需要移动元素才能将其放置在正确位置。为解决这个问题，你可以使用堆数据结构代替！

多路归并（也是你算法的普遍名称）通常使用另一种“合并”数据结构——锦标树（tournament-tree）来实现。你可以在Knuth的《计算机程序设计艺术》（排序章节，我记得）中找到描述。与堆相比，它在理论和实践中都具有更低的常数因子，特别是在这种情况下。

如果你想寻找实现代码，我相信GNU C++标准库parallel-extensions中的并行多路归并正是使用这种方式实现的。

编辑：我引用了错误的书名，已经修正。