是时候将排序列表合并到单个排序列表中？

给出logN每个大小的排序列表N*logN.将它们合并到单个排序列表所需的总时间是多少？

A) O(NlogN)
B) O(N)
C) O(NloglogN)
D) O(Nlog(N/logN))

我尝试通过N = 4来解决它.但没有选择令人满意.

1> Ron.B.I..：

---

我相信答案有点偏,我知道这样做的方法如下:

合并K个已排序的大小为M的列表使用Min Heap:

创建排序列表中前k个元素的MinHeap - 可以及时完成O(K).

虽然MinHeap不是空的:

2.1.取出最小的项目 - O(log(K))并将其放入已排序的输出中.

2.2.从列表中的下一个元素中获取2.1中的项目并将其添加到MinHeap中 - O(log(K))

时间复杂性: O(K) + O(K * M * log(K)) = O(K * M * log(K))

在我们的情况下:

O(K*M*log(K)) = O(log(N) * N * log(N) * log(log(N)) = O(N * log^2(N) * log(log(N))

编辑: 正如这里建议的,另一种方法是成对合并所有列表:

通过合并对来合并K个已排序的大小为M的列表:

将所有列表放在一个列表中L.

而| L |> 1:

2.1.将L分成对(a,b)并将列表a和b合并到c中 - 用于将是O(M)合并的大小为M的列表.

2.2.将所有合并列表(c)放入单个列表L(替换之前的L).

L中唯一的列表就是结果.

时间复杂度分析: 在每次迭代中,我们遍历所有元素 - O(MK)和合并,log(K)迭代将导致O(log(K)*MK)= O(N*log ^ 2(N)*log (日志(N))

---

FWIW,在这种情况下具有相同大小的列表,您可以在不使用堆的情况下实现相同的时间绑定:只需将第一个与第二个列表合并,将第三个与第4个列表合并,依此类推,然后继续合并为二进制 - 像时尚一样.您有日志K级别,每个级别都有工作K*M,总计为O(log K*K*M)