Здесь описана сложность исполнения основных операций над множествами.
Стоит обратить внимание на статью «Сложность операций со словарями» — реализация множеств намеренно весьма схожа с реализацией словарей.

На заметку
Далее n — количество элементов в контейнере.

Общие для множеств и статичных множеств операции имеют одинаковую сложность.

ОперацияСр. сложностьПримерПримечание
lenO(1)len(s)
.addO(1)s.add(5)
Проверка на входимостьO(1)x in sА у списков/кортежей — O(n).
.removeO(1)s.remove(5)А у списков/кортежей — O(n).
.discardO(1)s.discard(5)
.popO(1)s.pop(i)А у списков/кортежей — O(n).
.clearO(1)s.clear()Равно как и s = set().
СозданиеO(len(t))set(t)
Проверки ==, !=O((len(s))s != t
.issubsetO(len(s))s.issubset(t)
.issupersetO(len(t))s.issuperset(t)
.unionO(len(s)+len(t))s.union(t)
.intersectionO(min(len(s), len(t)))s.intersection(t)Заменить min на max, если t не множество.
.differenceO(len(s))s.difference(t)
.symmetric_differenceO(len(s))s ^ t
ПроходO(n)for v in s:
.copyO(n)s.copy()

На заметку
Если сравнивать со списками/кортежами, то многие одинаковые операции над множествами предлагают более привлекатетельную сложность O(1). Часто это объясняется тем, что множествам не требуется сохранять порядок элементов.
Синонимы поиска: Сложность операций со множествами
На заметку
Зарегистрированные пользователи могут публиковать свои мнения относительно Книг, Видео, Статей других авторов и прочего в разделе Обсуждений.