Сложность операций со словарями
Здесь описана сложность исполнения основных операций над словарями.
В таблице ниже приводится усреднённая сложность. Амортизированный худший случай обычно описывается
Указанная ниже сложность справледлива и для
O(n). Для усреднённой сложности предполагается, что хеш-функция для словарей в состоянии сделать конфликты редкими. Также предполагается, что ключи, используемые в параметрах, выбираются равномерно из множества всех существующих ключей. На заметку
Далее
n — количество элементов в контейнере; k — значение параметра, либо количество элементов в параметре.Указанная ниже сложность справледлива и для
defaultdict (вместе с доступными операциями они наследуют от словарей и их сложности). Предполагается, что конструирование нового defaultdict имеет сложность O(1) (что справледливо для часто используемых int(), list(), set()).| Обращение по индексу | O(1) | d[k] | |
| Присвоение | O(1) | d[k] = v | |
| len | O(1) | len(d) | |
| del | O(1) | del d[k] | |
| .setdefault | O(1) | d.setdefault(1) | |
| .pop | O(1) | d.pop(k) | |
| .popitem | O(1) | d.popitem() | |
| .clear | O(1) | d.clear() | То же: d = {} и d = dict(). |
| Представление | O(1) | d.keys() | |
| Создание | O(k) | dict(obj) | Зависит от числа кортежей (ключ, значение). |
| Проход | O(n) | for k in d: | То же для keys(), values(), items(). |
| .copy | O(n) | d1 = d.copy() |
На заметку
Для словарей, где ключи являются строками, используется быстрый путь. Это не оказывает влияния на алгоритмическую сложность, однако сильно влияет на постоянные факторы — то, на сколько быстро исполяется типовое приложение.
Синонимы поиска: Сложность операций со словарями
В разделе «Сложность операций в Python»:
Сложность операций со множествами
Сложность операций со списками
На заметку
Зарегистрированные пользователи могут публиковать свои Статьи.