logo标签列表

合并k个已排序链表 - 分析

algorithmmergelist
6
我正在考虑解决一个问题的不同方案。假设我们有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(KN)的时间。所以问题是-我是否出了问题，还是他实际上是错的？如果我是对的，为什么无法使用这种“分治”方法代替优先队列方法？
1
嗯，我猜它比priority_queue算法更糟糕，因为它使用了大量额外的内存。不过，它更容易实现... 嗯 :) - M. Williams
在这个问题中，N 定义了所有列表中元素的总数，而不是其中一个列表的平均元素数量。 - M. Williams
2
我能理解会有logK行，但是你能否解释一下为什么每一行都是O(n)？例如，在第一行中，不应该是k*O(n)吗？ - Sesh
无论使用什么策略，都会涉及到NK个元素。因此，复杂度无法从O(NK)降低。 - user3401643
4个回答
3
根据您的描述，这个过程确实是O(N log K)级别的。它可以运行，所以您可以使用它。
个人认为应该使用带有优先队列的第一个版本，因为我认为它会更快。从粗略的大O意义上来说，它并不更快，但我认为如果您实际计算出两者进行比较和存储所需的次数，第二个版本将需要多几倍的工作量。
3
如果您要合并少量列表，那么这种两两配对的方法比优先队列方法更快，因为每次合并操作非常少：基本上只有一个比较和每个项目的两个指针重新分配 (以移动到新的单链表)。正如您所示，其时间复杂度为 O(N log K)（处理每个N个项目需要log K步）。
但是最好的优先队列算法，我相信，在插入和删除方面的时间复杂度为O(sqrt(log K))或O(log log U)(其中U是可能不同优先级的数量)，如果您可以使用值来设置优先级而不是使用比较，则最好使用优先队列，例如给定整数优先级，并且K很大时。
我认为进行性能分析是值得的。理论分析有时可能会有所裨益，但通常我现在会尝试确定在什么K值之后，我的方法开始与优先队列方法相比较劣。感谢您的回答。 - M. Williams
1

这是 O(2*log(K)*N) 这是 O(N*log(K))，你不能有最坏的复杂度，因为你只在 O(log(K)) 中将 2N 次添加到优先队列中。

或者你可以在 O(2N) 中将所有元素推入向量中。并在 O(2n*log(2n)) 中进行排序。然后你就有了 O(2N+2N*Log(2N))，这是 O(N*LOG(N))，正好是你的 K = N；

一般来说，我只是想知道我的分析是否正确，而不考虑 N log K 前面的常数。如果这是代码中的瓶颈点，我可能会使用优先队列算法。 - M. Williams
0

它确实运行在O(N*log K)，但不要忘记，O(N*log K)是O(N*K)的子集。也就是说，你的朋友也没有错。

1
看起来这是一个保存我们友谊的绝佳方式 :)) - M. Williams
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接