пространственная сложность простой факториальной функции в python

Question

Какова должна быть пространственная сложность этой факторной функции в python?

def fact(n): 
    product = 1 

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

    return product 

Эта же идея на других языках, как C приведет к O (1) космической сложности, но для этого примера будет составлять (2, п + 1) приводит к пространственной сложности O (N) пространства сложности?

Answer 1

В py2.x range возвращает список, поэтому ваш for-loop фактически выполняет итерацию по этому списку. Следовательно, это 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, диапазон представляет собой генератор, как старый xrange в Python 2.

Так будет O (N), если вы используете Python 2.