我的python函数的空间复杂度是多少？

Question

有人能告诉我这个 python 函数的空间复杂度是多少吗？我相信它是 O(1) 但我的朋友告诉我这是 O(N)。

他们说 O(N) 的原因：您在 for 循环的每次迭代中都创建了一个新的“a”。

我说 O(1) 的原因：每次迭代并转储旧的 'a' 时，您都会创建一个新的 'a'。

def hello(n):
  for i in range(n):
    a = 10

如果这是伪代码，空间复杂度是否相同？

Answer 1

a只是一个变量，在这里你分配一个整数值，对于这一点，空间复杂度是 O(1)。

但我认为衡量的关键在于for i in range(n)陈述。

在python2 中，因为range(n)会创建一个包含 n 个元素的列表，所以空间复杂度为 O(n)。

在python3 中，range(n)将返回一个迭代器（不创建整个 n 长度列表），因此空间复杂度为 O(1)。