Какая алгоритмическая сложность вставки в множестве в Python

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

Пример:

s = set()
s.add(1)  # O(1) в среднем

Примечания:

• Если хеш-функция работает плохо (например, для сложных объектов), возможны деградации производительности.
• При частых коллизиях Python автоматически рехеширует множество, что временно увеличивает сложность.