Какие операции над множествами имеют низкую вычислительную сложность?

Основные операции с множествами и их сложность

Множества в Python реализованы на основе хеш-таблиц, что обеспечивает высокую производительность для базовых операций. Проверка вхождения элемента (оператор in) выполняется в среднем за O(1), так как элемент хешируется и сразу находится в таблице. Аналогично, добавление (add) и удаление (remove или discard) также имеют амортизированную сложность O(1).

Операции над несколькими множествами

Для операций, таких как объединение (|), пересечение (&) и разность (-), сложность составляет O(len(s)), где s — меньшее из множеств. Например, пересечение двух множеств требует проверки каждого элемента меньшего множества на вхождение в большее, что даёт O(min(len(a), len(b))).

Пример кода

a = {1, 2, 3, 4}
b = {3, 4, 5, 6}

# Проверка вхождения — O(1)
print(3 in a)  # True

# Объединение — O(len(a) + len(b))
union = a | b  # {1, 2, 3, 4, 5, 6}

# Пересечение — O(min(len(a), len(b)))
intersection = a & b  # {3, 4}

# Разность — O(len(a))
difference = a - b  # {1, 2}

Вывод

Множества идеально подходят для задач, где требуется быстрая проверка уникальности или частые операции поиска, например, при фильтрации данных или устранении дубликатов. Их использование оправдано, когда важна производительность и порядок элементов не имеет значения.