Сложность пространства при уменьшении входных данных

Question

Представьте, что вы хотите найти все дубликаты в массиве, и вы должны сделать это в 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.

Answer 1

Чтобы определить сложность пространства, вы должны кое-что знать о том, как реализовано pop, а также о том, как Python управляет памятью. Чтобы ваш алгоритм использовал постоянное пространство, arr должен был бы освободить память, используемую извлеченными объектами, и seen должен был бы иметь возможность повторно использовать эту память. Однако большинство реализаций Python , вероятно, не поддерживают этот уровень совместного использования. В частности, pop не собирается освобождать память; он не допустит необходимости в будущем, вместо того, чтобы просить вернуть память.

Answer 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 может иногда быть проблемой. Проверьте это сообщение для более подробной информации.