Сложность операций со множествами
Здесь описана сложность исполнения основных операций над множествами.
Стоит обратить внимание на статью «Сложность операций со словарями» — реализация множеств намеренно весьма схожа с реализацией словарей.
Общие для множеств и статичных множеств операции имеют одинаковую сложность.
На заметку
Далее
n — количество элементов в контейнере.Общие для множеств и статичных множеств операции имеют одинаковую сложность.
| Операция | Ср. сложность | Пример | Примечание |
|---|---|---|---|
| len | O(1) | len(s) | |
| .add | O(1) | s.add(5) | |
| Проверка на входимость | O(1) | x in s | А у списков/кортежей — O(n). |
| .remove | O(1) | s.remove(5) | А у списков/кортежей — O(n). |
| .discard | O(1) | s.discard(5) | |
| .pop | O(1) | s.pop(i) | А у списков/кортежей — O(n). |
| .clear | O(1) | s.clear() | Равно как и s = set(). |
| Создание | O(len(t)) | set(t) | |
Проверки ==, != | O((len(s)) | s != t | |
| .issubset | O(len(s)) | s.issubset(t) | |
| .issuperset | O(len(t)) | s.issuperset(t) | |
| .union | O(len(s)+len(t)) | s.union(t) | |
| .intersection | O(min(len(s), len(t))) | s.intersection(t) | Заменить min на max, если t не множество. |
| .difference | O(len(s)) | s.difference(t) | |
| .symmetric_difference | O(len(s)) | s ^ t | |
| Проход | O(n) | for v in s: | |
| .copy | O(n) | s.copy() |
На заметку
Если сравнивать со списками/кортежами, то многие одинаковые операции над множествами предлагают более привлекатетельную сложность O(1). Часто это объясняется тем, что множествам не требуется сохранять порядок элементов.
Синонимы поиска: Сложность операций со множествами
В разделе «Сложность операций в Python»:
Сложность операций со словарями
Сложность операций со списками
На заметку
Зарегистрированные пользователи могут добавлять Книги.