0

我有四个排序列表,我想将它们合并到一个排序列表中。
最有效的方法是什么?如果实现可以并行完成,那将是一个加号。

4

1 回答 1

4

这是合并排序的合并部分。

只需在每个列表的开头取四个元素中的最小值并将其转储到输出中。重复直到所有列表都为空。假设这min4是一个固定成本,那么这将是 O(N)。

如果您有更多信息(例如列表的范围),您可能可以稍微改进一下,但我认为这些不会影响渐近复杂度。

于 2012-07-04T12:39:03.417 回答