python - python中简单阶乘函数的空间复杂度

Question

python中这个阶乘函数的空间复杂度应该是多少？

def fact(n):
    product = 1

    for i in range(2, n+1):
        product = product * i

    return product

在其他语言（如 C）中，同样的想法会导致 O(1) 空间复杂度，但对于这个例子，range(2,n+1) 会导致 O(n) 空间复杂度的空间复杂度吗？

Answer 1

在 py2.x 中range返回一个列表，因此您的 for 循环实际上是在迭代该列表。因此，它是O(N)在内存方面。

您可以xrange在此处使用它一次返回一个项目。

帮助xrange：

xrange(start, stop[, step]) -> xrange object

Like range(), but instead of returning a list, returns an object that
generates the numbers in the range on demand.  For looping, this is 
slightly faster than range() and more memory efficient.

Answer 2

它还取决于您使用的是哪种 python。

在 python 3 中，range 是一个生成器，就像 python 2 中的旧 xrange。

因此，如果您使用的是 python 2，它将是 O(n)。