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

#python #space-complexity

Вопрос:

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

 input: nums = [1, 2, 3, 4, 5, 6, 7, 8....]
       m = integer 

for i in range(len(nums)):
    temp = nums[i:i m]

должна ли эта пространственная сложность выглядеть как o(m) или o(n*m), и почему? Спасибо!

Ответ №1:

Не включая ввод, с этим фрагментом кода, поскольку m он не кажется константой, это должно быть просто O(m) потому, что в любой данный момент времени мы храним только 1 фрагмент nums[i:i m] , потому temp что просто переназначается с новым подсписком для каждого цикла, что делает предыдущий подсписк уже подлежащим сборке мусора.

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

Но если вы сохраняете каждый подсписок, например:

 temp_list = []
for i in range(len(nums)):
    temp = nums[i:i m]
    temp_list.append(temp)

Тогда это должно быть O(m * len(nums)) потому, что мы будем хранить m элементы для каждого элемента внутри nums .

1. Я не нашел конкретного ответа о сборке мусора python, друг сказал, что это должно быть o(m n), так как python при каждом срезе запрашивал новую память для выделения срезанного массива, он сделал это o(m n), не уверен, правильно это или нет. Буду признателен за комментарии.

Ответ №2:

Игнорируя сборку мусора Python, вы получаете пространственную сложность O(mn) , где n = len(nums) . Это связано с тем, что сначала вы выделяете список n элементов, а затем выделяете n списки m элементов каждый (обратите внимание, что нарезка списка создает новое распределение). Это дает общее количество n mn выделенных ячеек, которое асимптотически O(mn) .

Но на все списки, созданные в цикле for, ссылаются temp . Это означает, что как только создается новый список, предыдущий список не имеет ссылок и становится пригодным для сбора мусора. Это оставляет нас практически с двумя списками: nums с длиной n и последним temp с длиной m , что равно сложности пространства O(m n) .