Какую временную сложность имеет алгоритм удаления дубликатов из списка с сохранением порядка?

Оценка сложности алгоритма дедупликации напрямую связана с используемыми структурами данных.

Базовое рассуждение

Перед перечислением важно зафиксировать: сложность считается по количеству операций относительно размера входных данных.

Временная сложность

1. Проход по списку

   • n итераций → O(n)

2. Проверка в set

   • среднее время O(1)

3. Добавление в set

   • среднее время O(1)

Итого:

• Временная сложность: O(n)

Пространственная сложность

1. Дополнительный set из n элементов

2. Результирующий список из n элементов

• Пространственная сложность: O(n)

Что может ухудшить сложность

1. Плохая хеш-функция

2. Коллизии

3. Нехешируемые элементы

Вывод

Алгоритм удаления дубликатов с сохранением порядка имеет линейную временную сложность и хорошо масштабируется на больших списках.