如何对k个有序链表进行排序？

Question

我正在阅读此处的解决方案：https://leetcode.com/problems/merge-k-sorted-lists/solution/，它介绍了如何将k个排序链表合并成一个链表。

一个简单的解决方案是编写一个函数来处理两个链接列表，并在第一个2个列表上调用它，然后再使用以前的结果和第3个链接列表调用它，然后再次使用以前的结果和第4个链接列表等等。

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

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

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

重复执行此过程，直到我们得到最终排序的链表。

我的问题是：为什么第二种方法更有效率？我不接受这个事实，因为我认为我们按不同的顺序执行相同的工作。那么优化来自哪里？我们使用了哪些事实使它更快？

我在最后一个评论中澄清了我的问题。

- user15278366

---

假设我们有四个链表，它们的大小分别为100、5、4和3。第一种策略会先将前两个链表合并，最多需要105次比较，然后再将其与第三个链表合并，最多需要105 + (105 + 4) = 214次比较，最后再将结果与第四个链表合并，最多需要214 + (214 + 3) = 429次比较。而两两合并法则会先将100和5合并，再将4和3合并，最多需要100+5 + 4+3 = 112次比较，最后再将105和12合并，最多需要117次比较。因此，将总共需要112 + 117 = 219次比较作为上限，这比429次要少。 - Telescope

@Telescope 你愿意把它作为答案添加吗？它可以再详细一些，但它已经基本回答了这个问题。 - cigien

@Telescope 谢谢，我从数学角度理解了这一点。但是，我的意思是为什么会发生这种情况？为什么一般来说成对进行联合比从左到右进行联合更好。我的大脑拒绝接受这一部分... - user15278366

为了直觉，您可以想象在每次合并中，较小的列表以较大的列表长度为代价被“消耗”，之后它变成了一个具有新长度的大型组合列表。因此，您希望以最小的成本消耗所有列表。因此，应通过使用最小成本的较小列表即短列表来完成。如果您熟悉它，它类似于5个人用30秒灯过桥的逻辑谜题。 - justhalf

Answer 1

假设第i个链表的长度为l[i]，所有链表的总长度为L。同时，我假设您（读者）知道两个有序列表的2路合并具有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总体上更好。

- LIU Qingyuan

Answer 2

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

1. 选择a和b，我们得到长度为[a+b,c,d]和total_steps = (a+b)。
2. 选择a+b和c，我们得到[a+b+c,d]和total_steps = (a+b)+(a+b+c) = 2*a + 2*b + c。
3. 最后，我们得到[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路合并）。

- Abhinav Mathur