排序 k 个有序链表？

Question

我正在阅读这里的解决方案：https://leetcode.com/problems/merge-k-sorted-lists/solution/ 关于如何将 k 个排序的链表合并为一个链表。

一个简单的解决方案是编写一个函数来完成 2 个链表的工作，在前 2 个链表上调用它，然后用前一个结果和第 3 个链表再次调用它，然后用前一个结果和第 4 个链表再次调用它列表等。

另一个更有效的解决方案是执行以下操作：

配对 k 个列表并合并每对。

第一次配对后，k 个列表合并成 k/2 个平均长度为 2N/k 的列表，然后是 k/4、k/8 等等。

重复这个过程，直到我们得到最终的排序链表。

我的问题是： 为什么第二种更有效率，我的头脑拒绝接受这个事实，因为我认为我们在不同的顺序做同样的工作。这种改进来自哪里？我们使用了哪些事实使其更快？

我在上一条评论中澄清了我的问题。

Answer 1

令链表的长度为[a,b,c,d]。通过贪婪地合并前两个列表，我们得到：

选择a和b，我们得到长度[a+b,c,d]和total_steps = (a+b)。
选择a+b和c，我们得到[a+b+c,d]和total_steps = (a+b)+(a+b+c) = 2*a + 2*b + c。
最后，我们得到[a+b+c+d]、total_steps = (2*a + 2*b + c) + (a+b+c+d) = 3*a + 3*b + 2*c + d

正如您从 total_steps 中注意到的那样，前两个列表（您开始合并的列表）具有最高的系数。如果任一列表的长度都比较长，则性能不会最佳（因为系数较大，如图所示）。更好的方法是 在每一步合并具有最小长度的列表 （或您问题中列出的 k 向合并）。

Answer 2

假设第i个链表的长度是l[i]，所有链表的总长度是L。我还假设您（reader）知道两个有序列表的双向合并具有 O(a+b) 时间复杂度，其中 a 是第一个列表的长度，b是秒的长度。

第二种解法（解法2）无论输入数据如何排列，时间复杂度稳定。在我们得到答案之前，任何链表的内容都被合并 log k 次，所以总时间复杂度在所有情况下都是 O(L log k)。

现在让我们考虑第一个解决方案（解决方案1）。考虑所有 l[i] 相等的情况（所有链表的长度相同），总时间成本 T 是

T = l[1] * k + l[2] * (k-1) + ... + l[k] * 1
  = l[1] * k(k+1) / 2
  = L * (k+1)/2

也就是说解1的最坏时间复杂度是O(Lk)，明显慢了

解决方案 1 的一个直接改进是根据列表的长度合并列表，但这并没有多大帮助。根据长度对列表进行排序不是免费的，在上述情况下，这显然无济于事，因此最坏情况下的时间复杂度没有提高。

解决方案 2 在最坏情况和大多数情况下更好。尽管您可以构造一个方案 1 更快的案例，但这并不意味着方案 1 总体上更好。

Ordering k ordered linked lists?