Quelle est la complexité temporelle de l'ajout d'un élément à un ensemble en Python?

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

Это достигается за счёт вычисления хэш-кода элемента и вставки его в соответствующую ячейку внутренней структуры. Однако в худшем случае (при большом количестве коллизий) сложность может деградировать до O(n), где n — количество элементов в множестве.

Пример:

s = set()
s.add(42)  # Добавление элемента выполняется примерно за O(1)