c++ - 排序 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

假设第i个链表的长度是l[i]，所有链表的总长度是L。此外，我假设您(读者)知道两个有序列表的双向合并具有 O(a+b) 时间复杂度，其中 a 是第一个列表的长度list 和 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 总体上更好。