Космическая сложность (Python)

Question

У меня есть вопрос, предположительно, сложность времени и пространства для gdc (i, n) равна O (1), какова сложность пространства для этой функции?Сложность времени равна O (n) из-за цикла for.Как насчет космической сложности?Ответ 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, он создает генератор.

ОБНОВЛЕНИЕ: Как сказал Вайнс, диапазон не является итератором.Извините за ввод в заблуждение.

Согласно документации:

Преимущество типа диапазона по сравнению с обычным списком или кортежем состоит в том, что объект диапазона всегда будет занимать одинаковое (небольшое) количествопамяти, независимо от размера диапазона, который он представляет (поскольку он хранит только значения начала, остановки и шага, вычисляя отдельные элементы и поддиапазоны по мере необходимости).