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

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的列表，必须完全迭代。但我看到这种情况的唯一一次是在我上面解释的段落中。我觉得我可能是完全的误解，任何澄清将不胜感激。

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

不重要的是，什么是在点，或这些名单有多长。仅仅因为它们以这种方式结束，就意味着不可能通过将一个列表的最后一块附加到另一个列表中来“快捷”合并操作。

还有许多“中间”的情况，这不是最坏的情况，但也不是最好的情况，即一个列表中的一个块可以连接到结果，而不分别抓取该块中的每个节点，但是这个块可能只有两个节点，或者three...etc。

这意味着平均时间复杂度也将是O(n+m)。这可能不太明显，但在没有进一步检查的情况下，将其中一个列表中的相当大的部分连接起来的可能性很低。它变得越低，那块必须是更大。