这里的 space 复杂度 O(m+n) 怎么样？

Question

合并两个排序的链表并return它作为一个新的链表。新列表应该由前两个列表的节点拼接而成。

class Solution:
    def mergeTwoLists(self, l1, l2):
        if l1 is None:
            return l2
        elif l2 is None:
            return l1
        elif l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2

我知道跟堆栈有关系。有人可以帮我说清楚吗？我是新手，谢谢。

Answer 1

该算法的基本原理是每次递归调用都会从 l1 或 l2 中选取一个元素。由于这只能发生 M + N 次，时间复杂度将为 O(M + N).

space 复杂性是另一回事。

I know it has something to do with the stack.

是的。在 Python 中，递归调用需要每个递归级别的堆栈帧。堆栈帧包含调用参数和局部变量，以及允许调用 return 到调用它的代码中的正确位置所需的信息。

在您的示例中，有 M + N 个级别，因此堆栈 space 的 space 复杂度为 O(M + N)。

假设您的链表节点以明显的方式实现，您的合并方法正在改变 l1 和 l2 对象，并且不再消耗 space。

许多语言/编译器支持称为尾调用优化 的东西，适用于递归调用自身的方法的许多情况。在可能的情况下，递归调用被优化为跳转到方法的开头，而不是使用调用指令。因此不需要栈帧。

在您的示例中，堆栈使用的 space 复杂度将是 O(1)。

但是Python不支持这个；见 Does Python optimize tail recursion?

这里的 space 复杂度 O(m+n) 怎么样？

How is the space complexity O(m+n) here?

python-3.x

recursion

linked-list

space-complexity