空间复杂性(Python)

Question

我有一个问题，假设gdc(i，n)时间和空间复杂度是O(1)，这个函数的空间复杂度是多少？由于一个for循环，时间复杂度为O(n)。空间的复杂性如何？答案是O(1)但我不明白为什么..。结果在for循环中取n个空间，所以不是O(n)吗？

def gcd_fun(n):
   for i in range(1, n+1):
      result += gcd(i, n)
   return result

Answer 1

这取决于您的python版本。如果您使用python 2，它将为range函数创建列表。列表分别需要O(n)内存复杂度。否则，如果使用python 3，它将创建生成器。

更新:正如Vineeth所说，range不是迭代器。抱歉误导你。

根据文件：

与常规列表或元组相比，range类型的优点是，range对象将始终占用相同(小)内存量，而不管它所代表的范围的大小(因为它只存储开始值、停止值和步骤值，根据需要计算单个项和子范围)。