我正在考虑针对一个问题的不同解决方案。假设我们有 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)
时间。所以,问题是——我是在什么地方搞砸了还是他真的错了?如果我是对的,为什么不能使用这种“分而治之”的方法来代替优先队列方法?
最佳答案
如果要合并的列表数量较少,这种成对方案可能比优先级队列方法更快,因为每次合并的操作极少:基本上每个项目只有一次比较和两次指针重新分配(转移到一个新的单链表)。正如您所展示的,它是 O(N log K)
(log K
个步骤处理 N
个项目)。
但我认为,最好的优先级队列算法是 O(sqrt(log K))
或 O(log log U)
用于插入和删除(其中 U
是可能的不同优先级的数量)——如果你可以用一个值来确定优先级而不是必须使用比较——那么如果你正在合并可以给出的项目,例如整数优先级,并且 K
很大,那么您最好使用优先级队列。
关于algorithm - 合并k个排序链表——分析,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2705366/