Сложность пространства при уменьшении ввода
Представьте, что вы хотите найти все дубликаты в массиве, и вы должны сделать это в O(1) пространстве и O(N) времени.
Такой алгоритм будет иметь O(N) пробел:
def find_duplicates(arr):
seen = set()
res = []
for i in arr:
if i in seen: res.append(i)
seen.add(i)
return res
Мой вопрос заключается в том, будет ли следующий алгоритм использовать O(1) пробел или O(N) пробел:
def find_duplicates(arr):
seen = set()
res = []
while arr:
i = arr.pop()
if i in seen: res.append(i)
seen.add(i)
return res
Технически arr становится меньше, и сумма |seen| и |arr| всегда будет меньше, чем исходное |arr|, но, в конце концов, я думаю, что для |arr| все еще выделяется seen место.
Я думаю, у вас есть небольшое представление о большой нотации O. Прочитай это и пойми, мой брат. удачи. datacamp.com/community/tutorials/…
Вы могли бы получить O(1) пространственную сложность еслиseen, повторно используя пространство, оставшееся ненужным arr. Но это не так. arr.pop() не обязательно освобождает память Любые; он сохраняется, чтобы избежать необходимости перераспределения памяти для будущих дополнений к arr.
@chepner, не могли бы вы написать ответ? Вопрос выглядит так, будто он связан с тем, освобождает ли .pop() какую-либо память. Я предполагаю, что для небольших массивов это будет ~ O(N) пространство, но затем, как только вы нажмете на большие массивы, pop() высвободит больше памяти и приведет к O(1)
Ответы 2
Всякий раз, когда вы пытаетесь выполнить анализ временной и пространственной сложности, подумайте о тестовом примере, который может взорвать вашу программу больше всего.
Ваша космическая сложность равна O(N). В случае вашей второй программы, если у вас есть список чисел только с 1 с. Например: x = [1,1,1,1,1,1,1]. Тогда вы увидите, что res вырастет почти до размера N. Подумайте, что произойдет, если у вас есть все разные числа. x = [1,2,3,4,5,6,7,8]. Теперь seen вырастает до размера N.
Кроме того, если подумать о временной сложности, функция pop() списков Python иногда может быть проблемой. Проверьте этот сообщение для более подробной информации.
Чтобы определить сложность пространства, вы должны кое-что знать о том, как реализован pop, а также о том, как Python управляет памятью. Чтобы ваш алгоритм использовал постоянное пространство, arr должен освободить память, используемую извлеченными элементами, а seen должен иметь возможность повторно использовать эту память. Однако большинство реализаций Python наверное не поддерживают такой уровень совместного использования. В частности, pop не собирается освобождать память; он будет удерживать ее от возможности необходимости в ней в будущем, вместо того, чтобы просить вернуть память.
Вы правы в своем анализе. Как вы сказали, космическая сложность равна O (n), потому что
seenрастет с вводом. Вы также можете рассмотреть случай, когда в массиве уже есть все уникальные целые числа. В худшем случае для вашего второго подхода по-прежнему O (n).