Время и пространство сложность для удаления дубликатов из списка

Question

У меня есть следующий код, и я пытаюсь получить сложность времени.

seen = set()
a=[4,4,4,3,3,2,1,1,1,5,5]
result = []
for item in a:
    if item not in seen:
        seen.add(item)
        result.append(item)
print (result)

Насколько я понимаю, когда я получаю доступ к списку, сложность времени для этой операции будет O(n), Как и в случае блока каждый раз, когда я смотрю на набор, и это будет стоить другого O(n), Такова общая сложность времени O(n^2)? Ли set.add() также добавить к сложности?

Кроме того, с космической сложностью это O(n)? Поскольку размер набора увеличивается каждый раз, когда он встречает новый элемент?

Любой вклад или ссылки, чтобы получить правильное представление о времени и сложности пространства приветствуется.

Answer 1

Наборы в Python реализованы в виде хеш-таблиц (аналогично словарям), поэтому оба in а также set.add() О (1). list.append() также O(1) амортизируется.

В целом, это означает, что сложность по времени составляет O (n) из-за итерации по a,

Сложность пространства также равна O(n), поскольку максимальное требуемое пространство пропорционально размеру входных данных.

Полезную ссылку на временную сложность различных операций над коллекциями Python можно найти по адресу https://wiki.python.org/moin/TimeComplexity и в разделе PyCon The Mighty Dictionary предоставляет интересное описание того, как Python достигает O(1). сложность для различных операций над множествами и диктовками.