我有些困惑,不理解合并两个有序链表的时间复杂度为什么是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的两个列表。但是,我只在我上面解释的段落中看到这种情况发生。我觉得我可能完全误解了,任何澄清都会受到赞赏。