Сложность операций со списками
Здесь описана сложность исполнения основных операций над списками.
Под капотом списки представлены в виде массивов. Наибольшие затраты происходят при необходимости дополнить список (когда изначально выделенной под него памяти недостаточно, все элементы придётся переместить в другое место), либо при вставке/удалении элемента близко к началу (последующие элементы потребуется переместить назад).
Далее
На заметку
Если требуется оптимизированная возможность вставки/удаления с обоих концов, вместо списков используйте
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»:
Сложность операций со множествами
Сложность операций со словарями
На заметку
У нас есть представительство в Facebook. Ссылка в самом низу страницы.