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

Question

Уже существует вопрос относительно этого, и ответ говорит, что асимптотическая сложность равна O (n). Но я заметил, что если несортированный список преобразуется в набор, набор можно распечатать в отсортированном порядке, что означает, что в какой-то момент в середине этих операций список был отсортирован. Тогда, поскольку любая сортировка сравнения имеет нижнюю границу Omega (n lg n), асимптотическая сложность этой операции также должна быть Omega (n lg n). Так в чем же состоит сложность этой операции?

Answer 1

Набор в Python - это неупорядоченная коллекция , поэтому любой заказ, который вы видите, происходит случайно. Поскольку и dict, и set реализованы как хеш-таблицы в CPython, вставка - это средний случай O (1) и наихудший случай O (N).

Так что list(set(...)) всегда означает O (N) иset(list(...)) - средний регистр O (N).

Вы можете просмотреть исходный код для set здесь .