Сложность операций со списками
Здесь описана сложность исполнения основных операций над списками.
Под капотом списки представлены в виде массивов. Наибольшие затраты происходят при необходимости дополнить список (когда изначально выделенной под него памяти недостаточно, все элементы придётся переместить в другое место), либо при вставке/удалении элемента близко к началу (последующие элементы потребуется переместить назад).
Далее
На заметку
Если требуется оптимизированная возможность вставки/удаления с обоих концов, вместо списков используйте
collections.deque
.На заметку
Общие для списков и кортежей операции имеют одинаковую сложность.
Далее
n
— количество элементов в контейнере; k
— значение параметра, либо количество элементов в параметре.Обращение по индексу | O(1) | l[i] | |
Присвоение | O(1) | l[i] = 0 | |
len | O(1) | len(l) | |
.append | O(1) | l.append(5) | |
.pop | O(1) | l.pop() | То же что и l.pop(-1) — выброс с конца. |
.clear | O(1) | l.clear() | |
Срез | O(b-a) | l[a:b] | |
.extend | O(k) | l.extend(a) | |
Создание | O(k) | list(a) | |
Проверки ==, != | O(n) | l1 == l2 | |
.insert | O(n) | l.insert(0, 5) | |
del | O(n) | del l[i] | То же и с удалением среза. |
.remove | O(n) | l.remove(...) | |
Проверка на входимость | O(n) | x in l | Проход по списку. |
.copy | O(n) | l.copy() | То же что и l[:]. |
.pop | O(n) | l.pop(i) | |
min, max | O(n) | min(l) | |
.reverse | O(n) | l.reverse() | |
Проход | O(n) | for v in l: | |
Присвоение среза | O(k+n) | l[... : ...] = ... | |
.sort | O(n log n) | l.sort() | |
Умножение | O(k×n) | i l |
Синонимы поиска: Сложность операций со списками
В разделе «Сложность операций в Python»:
Сложность операций со множествами
Сложность операций со словарями
На заметку
У нас есть новостная группа в Telegram. Там же можно обсудить интересующие вопросы. Ссылка в самом низу страницы.