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

Question

Алгоритм работает за O(n), где n — длина списка. Каждый элемент обрабатывается один раз. Проверка наличия элемента в set выполняется за O(1) в среднем. Поэтому общее время линейное. Память также используется линейно.

YeaHub · Accepted Answer

Оценка сложности алгоритма дедупликации напрямую связана с используемыми структурами данных.Базовое рассуждениеПеред перечислением важно зафиксировать: сложность считается по количеству операций относительно размера входных данных.Временная сложностьПроход по спискуn итераций → O(n)Проверка в setсреднее время O(1)Добавление в setсреднее время O(1)Итого:Временная сложность: O(n)Пространственная сложностьДополнительный set из n элементовРезультирующий список из n элементовПространственная сложность: O(n)Что может ухудшить сложностьПлохая хеш-функцияКоллизииНехешируемые элементыВыводАлгоритм удаления дубликатов с сохранением порядка имеет линейную временную сложность и хорошо масштабируется на больших списках.