Cos*_*ert 6 algorithm merge list
我正在考虑针对一个问题的不同解决方案.假设我们有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).
我的朋友(两天前)告诉我这需要O(K N)时间.所以,问题是 - 我是否已经在某处或者他真的错了？如果我是对的,为什么不能使用这种"分而治之"的方法而不是优先队列方法？
如果要合并的列表数量较少，则这种成对方案可能比优先级队列方法更快，因为每次合并的操作极少：基本上每个项目只有一次比较和两次指针重新分配（转移到一个新的单项） -链表）。正如您所展示的，它是O(N log K)（每个log K处理项目的步骤）。N
但我认为，最好的优先级队列算法是O(sqrt(log K))用于O(log log U)插入和删除（其中U可能有不同优先级的数量）——如果您可以使用值确定优先级而不是必须使用比较——所以如果您要合并项目可以给出例如整数优先级，并且K很大，那么您最好使用优先级队列。