algorithm - 合并k个排序链表——分析

Question

我正在考虑针对一个问题的不同解决方案。假设我们有 K 个排序的链表，我们正在将它们合并为一个。所有这些列表共有 N 个元素。

众所周知的解决方案是使用优先级队列并从每个列表中弹出/推送第一个元素，我可以理解为什么它需要 O(N log K) 时间。

但是让我们来看看另一种方法。假设我们有一些 MERGE_LISTS(LIST1, LIST2) 过程，它合并两个排序列表，它会花费 O(T1 + T2) 时间，其中 T1 和 T2 代表 LIST1 和 LIST2 大小。

我们现在所做的通常是将这些列表配对并逐对合并它们(如果数字是奇数，例如，最后一个列表可以在第一步中忽略)。这通常意味着我们必须制作以下合并操作“树”:

N1, N2, N3... 代表LIST1, LIST2, LIST3 尺寸

• O(N1 + N2) + O(N3 + N4) + O(N5 + N6) + ...
• O(N1 + N2 + N3 + N4) + O(N5 + N6 + N7 + N8) + ...
• O(N1 + N2 + N3 + N4 + .... + NK)

很明显，这些行将有 log(K) 行，每一行都实现了 O(N) 操作，所以 MERGE(LIST1, LIST2, ... , LISTK) 操作实际上等于 O(N log K)。

我 friend 告诉我(两天前)这需要 O(K N) 时间。所以，问题是——我是在什么地方搞砸了还是他真的错了？如果我是对的，为什么不能使用这种“分而治之”的方法来代替优先队列方法？

Answer 1

如果要合并的列表数量较少，这种成对方案可能比优先级队列方法更快，因为每次合并的操作极少:基本上每个项目只有一次比较和两次指针重新分配(转移到一个新的单链表)。正如您所展示的，它是 O(N log K)(log K 个步骤处理 N 个项目)。

但我认为，最好的优先级队列算法是 O(sqrt(log K)) 或 O(log log U) 用于插入和删除(其中 U 是可能的不同优先级的数量)——如果你可以用一个值来确定优先级而不是必须使用比较——那么如果你正在合并可以给出的项目，例如整数优先级，并且 K 很大，那么您最好使用优先级队列。