使用合并 2 个排序列表的概念合并 k 个排序链表的时间复杂度是多少？

Question

我想知道如果我使用合并2个排序链表的算法merging k sorted lists的真实时间复杂度

我在某处看到时间复杂度为 O(nk)，在某处为 O(nk^2)。 （k 是排序列表的数量，n 是列表中元素的数量）。 所以我对这个问题的时间复杂度感到困惑。

请告诉我这个问题的真实时间复杂度。

Answer 1

I want to know the true time complexity of merging sorted lists if I use the algorithm of merging 2 sorted linked lists.

有多种算法可供选择。

我们定义为一个排序列表中值的（最大）数量，因此值的总数以 为界。的明确定义很重要，因为有些人会将其定义为所有列表中值的 总数 - 这显然会导致不同的公式。我将把值的总数定义为 。所以=

朴素算法

此算法合并前两个列表，然后将结果与第三个列表合并，然后将结果与第四个列表合并，...等等

该算法需要执行-1次合并，每次合并涉及的项目都比前一次多。第一次合并涉及两个元素列表，所以是O(2)

因此我们有以下关系：

(2) = O(2)
() = (−1) + O()

等等：

() = O(∑_=2..) = O(²) = O()

最后一步使用triangular numbers

的公式

分而治之算法

（二进制）分而治之算法定义了只有 2 个列表时的基本情况，并将它们与已知算法合并。在所有其他情况下，它合并来自递归的两个列表。这确实是 merge sort 使用的原则。

现递归关系如下：

(2) = O(2)
() = 2(/2) + O()

如果我们将这个关系展开一次，我们得到：

() = 2(2(/4) + O(/2)) + O() = 4(/4) + O() + O()

再展开的话：

() = 8T(/8) + O(3)

log₂ − 1 次扩展后：

() = (/2)(2) + O(log)

代入(2)，我们得到：

() = O() + O(log) = O(log) = O(log)

基于堆的算法

当您创建一个二进制最小堆时，其中每个条目都是一个链表，以其第一个节点的值为键，然后您可以重复从具有最小元素的堆中拉出列表，从中提取该元素该列表，并将该列表再次插入堆中，它将根据其新键找到它的位置（因为它现在少了一个节点）。如果列表变空，则不再将其插入堆中。

构建堆的成本为 O()。一个堆提取和插入成本为 O(log)。有提取要做，所以复杂度为 O() + O(log) = O(log) = O(log)