空间复杂性（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版本。如果您使用的是python2，它将为range函数创建列表。分别，list需要O（n）内存复杂度。否则，如果使用的是python3，它将创建生成器。在

更新：正如Vineeth所说的range不是迭代器。很抱歉误导你。在

根据文件：

The advantage of the range type over a regular list or tuple is that a range object will always take the same (small) amount of memory, no matter the size of the range it represents (as it only stores the start, stop and step values, calculating individual items and subranges as needed).