分析 Space 递归函数的复杂度

Question

在我们的 CS 课程中，我们没有介绍如何分析 space 复杂性。不过，我们的任务是实现 $\Theta(n)-time$ 算法来反转单向链表，最大 $O(1)-space$（除了实际数组）。

这是我在 Python 中的实现：

#x0.next = x1
def invert(x0,x1):
    next = x1.next
    x1.next = x0
    if next is None:
        return x1
    else:
        invert(x1,next)

def invertSLinkyList(head):
    firstNext = head.next
    head.next = None
    x = 0
    x = invert(head,firstNext)
    return x

给出一个快速的口头描述：本质上，我们遍历每个节点 (x0) 并将其下一个 (x1) 设置为前一个节点。然后我们在 its 下一个 (x1.next) 的原始下一个 (x1) 上递归调用它，直到我们到达结束节点 (其中有 next = None) 在这种情况下我们 return 这个节点作为新的头。

我分析它的时间复杂度是 $\Theta(n)$ 基于：

每次调用都会在恒定时间创建 1 child 个音符
当代码遍历整个列表时，我们创建了 n children。
需要 $O(1)$ 才能“合并”

那么我的问题是；我该如何分析它的 space 复杂性？

OBS：请注意，这不是评分作业。这是我每周训练的一部分。

Answer 1

分析space复杂度，你在分析内存量是否依赖于n。换句话说，随着算法输入大小的变化，在这种情况下 LL 的节点数会影响使用的 space 吗？

在这种情况下，通过使用递归，您可以将帧添加到调用堆栈并以这种方式使用内存。既然你提到你对每个节点进行了递归调用，你能推断出space的复杂性吗？这与您的参赛作品有什么关系？

在这种情况下，在 next 为 none 之前，您不会 return，此时将向调用堆栈添加多少堆栈帧？

在这种情况下，n 帧将被放入调用堆栈，因此您将获得 Space 复杂度 O(n)

分析 Space 递归函数的复杂度

Analyzing Space Complexity of Recursive Function

storage

complexity-theory