while 循环中列表的 space 复杂度是多少？

Question

我相信 similar question 已被要求 Java 但我不确定是否同样适用于 Python 因为我们没有明确使用 new关键字

对于这个特定的代码：

x = 5
while (x > 0):
  arr = []
  arr2 = []
  arr.append(1)
  arr2.append(2)
  x -= 1

执行此代码后，是否会创建总共 10 个不同的列表，这是一个 space 复杂度的 O(10)，还是只会创建 2 个列表，这是一个space 复杂度为 O(2)。我了解总体 space 复杂度仍然为 O(1)，但只是想了解幕后发生的事情。

Answer 1

首先，由于你在 while 循环中写了 arr = []，它会重写之前的数组，因此 arr 和 arr2 最多只有 1 个元素

其次，根据 Big-O 复杂度的正式定义，O(1) 和 O(2) 被认为是相同的常数复杂度，Big-O 复杂度旨在与变量一起使用以捕获相对于一个变量。

如果您想知道 python 是否使用您的代码创建了一个新数组，您可以覆盖默认列表对象以记录它的操作：

class ilist(list):
    def __init__(self, r=list()):
        print("Making new list: " + str(r))
        list.__init__(self, r)

    def __del__(self):
        print("Deleting list")


x = 5
while (x > 0):
    arr = ilist()
    arr2 = []
    arr.append(1)
    arr2.append(2)
    x -= 1
print("Finished while")

输出：

Making new list: []
Making new list: []
Deleting list
Making new list: []
Deleting list
Making new list: []
Deleting list
Making new list: []
Deleting list
Finished while
Deleting list

如您所见，它确实每次都创建和删除数组，因为该数组仅在 while 块内创建和使用。但它的行为应该如此，如果你打算创建它一次，那么你应该在外部范围内声明它。

while 循环中列表的 space 复杂度是多少？

What is the space complexity of a list in a while loop?

python

list

while-loop

space-complexity