时间戳

首页 > 解决方案 > 这里的空间复杂度 O(m+n) 如何？

python-3.x - 这里的空间复杂度 O(m+n) 如何？

问题描述

合并两个排序的链表并将其作为新列表返回。应该通过将前两个列表的节点拼接在一起来制作新列表。

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

我知道这与堆栈有关。有人可以为我说清楚吗？我是新手，谢谢。

标签： python-3.xrecursionlinked-listspace-complexity

解决方案

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

空间复杂度是另一回事。

我知道这与堆栈有关。

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

在您的示例中，存在M + N级别，因此堆栈空间的空间复杂度为O(M + N).

假设您的链表节点以明显的方式实现，您的合并方法正在改变l1andl2对象，并且不会消耗更多空间。

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

在您的示例中，堆栈使用的空间复杂度为 O(1).

但是 Python不支持这个；请参阅Python 是否优化尾递归？

推荐阅读