Какова сложность поиска и вставки элемента в множество (`set`)?

Для Python set поиск и добавление в среднем выполняются за O(1), но в худшем случае могут потребовать O(n). Вставка также иногда вызывает расширение хеш-таблицы.

Оценки предполагают хорошее распределение хешей и ограниченную стоимость hash/eq. При большом числе коллизий приходится проверять много элементов. Полный обход занимает O(n), а добавление уже существующего значения не создаёт дубликат. Элементы должны быть hashable; изменяемые list и dict напрямую не подходят. Операция поиска не зависит от сортировки, поскольку set не является упорядоченным деревом. Для оценки реальной скорости учитывайте тип ключей и объём памяти.