这个Python算法的空间复杂度是多少？

Question

def list_copy_rec(list_1, i):
    if i == len(list_1):
        return []  
    return [list_1[i]] + list_copy_rec(list_1, i + 1)

我不确定空间复杂度是多少。

算法非常简单，其目的是将输入的列表复制到另一个列表。它使用堆栈递归，我认为空间复杂度是 O(n)，但我不太确定，因为 + 运算符每次都会创建一个额外的列表（但可能会被垃圾收集器删除），而且事实上鉴于它是堆栈递归，它使用内存来保存未完成的操作直到结束（但我再次不确定这是否会影响最终的内存使用）。我是分析算法复杂性主题的初学者，所以请友善:)

Answer 1

您是正确的，该算法使用递归，并且每个递归调用都会向堆栈添加一个新帧。因此，对于长度为 (n) 的列表，堆栈深度将为 (O(n))。这解释了空间复杂性的第一个组成部分。

关于创建新列表的

+

运算符：虽然每次递归调用都会创建一个新列表，但旧列表在不再使用后将被垃圾回收。然而，所有这些列表大小的总和仍然会影响整体空间复杂性。

结合这两个因素，整体空间复杂度为 (O(n) + O(n) = O(n))。

所以，是的，你是对的：空间复杂度是 (O(n))。