合并两个有序链表的时间复杂度

Question

我有些困惑，不理解合并两个有序链表的时间复杂度为什么是O(m+n)。

唯一让我理解时间复杂度为O(m+n)的方法是，我们有两个如下所示的列表：1,3,5,7和2,4,6,8，并且我们交替获取其中的元素。在这种情况下，我认为这两个列表需要是相同长度的，因为如果它们长度不同，我们将完全迭代一个列表，然后只需将另一个列表的剩余部分附加到我们的新有序列表上即可。但在这种情况下，我们需要完全迭代每个列表。

此外，如果有一个有序列表L1，其中每个元素都小于另一个列表L2中的所有元素，则时间复杂度为O(n)，其中n是L1的长度。在这种情况下，我们永远不需要迭代L2。 我想知道我的时间复杂度分析是否正确？我在其他在线来源中读到，时间复杂度是O(m+n)，因为我们必须完全迭代长度分别为m和n的两个列表。但是，我只在我上面解释的段落中看到这种情况发生。我觉得我可能完全误解了，任何澄清都会受到赞赏。

- muddymosley

---

你所指的“sort”是指“合并（merge）”吗？ - Paul Sanders

是的，我确实是指合并。 - muddymosley

Answer 1

我理解 O(m+n) 时间复杂度的唯一方法是，我们有两个列表，如 1,3,5,7 和 2,4,6,8，我们交替从中获取。是的，在这种情况下，您需要 m+n 步。 在这种情况下，我认为这些列表需要具有相同的大小，因为如果它们大小不同，我们将完全迭代一个列表，然后只需将另一个列表的剩余部分附加到新排序的列表上。但在这种情况下，我们需要完全迭代每个列表。 这在您给出的示例中是正确的。但还有其他情况需要单独抓取所有节点。例如，当您合并 1,2,3,4,5,100 和 6,7,8,9 时，也可能发生这种情况。 我认为如果我们有一个有序列表 L1，其中每个元素都小于另一个列表 L2 中的所有元素，则时间复杂度为 O(n)，其中 n 是 L1 的长度。在这种情况下，我们永远不必迭代 L2。 这是正确的，并且这将被视为“最佳情况”的时间复杂度。 我在其他在线来源中读到，时间复杂度是 O(m+n)，因为我们必须完全迭代长度分别为 m 和 n 的两个列表。 有不同的方法来讨论时间复杂度。当除了 m 和 n 之外，输入中还可能有变化（在这种情况下是列表中的实际值）时，我们可以讨论最坏、平均和最佳情况的时间复杂度。如果未明确指定，则作者可能会提到最坏情况的时间复杂度，然后说它是 O(m+n) 是正确的，即使我们知道最佳情况的复杂度是 O(min(m, n))。 但我唯一看到发生这种情况的情况是我上面解释的那段话。 存在许多更多的情况，其中最坏情况发生。共同因素是其中一个列表以两个值结束，以便另一个列表的尾部应该按顺序位于这两个值之间。列表的大小对于该属性为真并不重要。 例如：

L1: ..................... 100, 102
L2: .................. 101

无论这些点中有什么，或者这些列表有多长，只是因为它们以这种方式结束意味着没有可能通过将一个列表的最后一块附加到另一个列表来“捷径”合并操作。

还有许多“中间”情况，它们不是最坏的情况，但也不是最好的情况，即其中一个列表的一块可以连接到结果而不必单独抓取该块中的每个节点，但该块可能仅有两个节点、三个节点等。

这意味着平均时间复杂度也将是O(n+m)。这可能不太明显，但是相对较大的一个列表块可以被连接而不需要进一步检查的概率很低。这个概率随着该块的大小增加而降低。

- trincot