0

我收到了一项作业，要求我有效地将总共有 N 个元素的 K 个排序列表合并到一个排序列表中。我偶然发现的方法是使用最小堆对 K 列表中的元素进行排序或使用分而治之的方法（成对合并）。该线程中的评论表明，分治法的时间复杂度为 O(NK)，而最小堆法的时间复杂度为 O(N log K)，并且两者具有相同的空间复杂度。我还访问了许多其他线程，但我无法获得清晰的图片。

疑问和问题：

  1. 许多其他站点告诉分治法和最小堆方法都有 O(N log K) 的时间复杂度。这是真的还是假的？
  2. 两种方法的空间复杂度是否相同？如果不是，它们有何不同？
  3. 为什么对于不同长度的列表，最小堆方法比分治法更好？
  4. 我还发现您可以使用优先队列来解决问题。与这些相比如何？
4

1 回答 1

2

该线程是关于K-way合并的。也就是说，您查看所有K列表的第一个值，然后从一个列表中取出一个元素并重复。

是时候O(n K)了，因为对于每个n元素，您都在寻找K列表的最小值。

Divide and mergeO(n)用于一组合并，这将列表的数量减少了一半。所以log(K)合并后你及时完成O(n log(K))。

min-heap 类似于K-way 合并，只是它只需要时间O(1)来找到最小的元素并将O(log(K))其取出。所以需要时间O(n log(K))。

最小堆是优先级队列的实现，所以它是一样的。

所有这些方法都占用相同的空间，O(n).

祝你编码好运，无论你选择哪一个！

于 2020-03-31T22:23:58.243 回答