Python time complexity
List
Внутри список представлен как массив; самые большие затраты связаны с выходом за пределы текущего размера (потому что приходится сдвигать весь массив) или со вставкой или удалением где-то в начале списка (по той же причине). Если нужно добавлять/удалять с обоих концов, то лучше использовать [deque]
| Operation | Average Case | Amortized Worst Case |
| Copy | O(n) | O(n) |
| Append[1] | O(1) | O(1) |
| Pop last | O(1) | O(1) |
| Pop intermediate[2] | O(n) | O(n) |
| Insert | O(n) | O(n) |
| Get Item | O(1) | O(1) |
| Set Item | O(1) | O(1) |
| Delete Item | O(n) | O(n) |
| Iteration | O(n) | O(n) |
| Get Slice | O(k) | O(k) |
| Del Slice | O(n) | O(n) |
| Set Slice | O(k+n) | O(k+n) |
| Extend[1] | O(k) | O(k) |
| Sort | O(n log n) | O(n log n) |
| Multiply | O(nk) | O(nk) |
| x in s | O(n) | |
| min(s), max(s) | O(n) | |
| Get Length | O(1) | O(1) |
| Concatenate two lists | O(n + m) | O(n + m) |
[deque]
Deque (двусторонняя очередь) внутренне представляется как двусвязный список. (список массивов, а не объектов, для большей эффективности) Оба конца доступны для операций. Поиск, выбор, добавление и удаление элементов из середины очень медленные.
| Operation | Average Case | Amortized Worst Case |
| Copy | O(n) | O(n) |
| append | O(1) | O(1) |
| appendleft | O(1) | O(1) |
| pop | O(1) | O(1) |
| popleft | O(1) | O(1) |
| extend | O(k) | O(k) |
| extendleft | O(k) | O(k) |
| rotate | O(k) | O(k) |
| remove | O(n) | O(n) |
Set
Реализация множества похожа на словарь
| Operation | Average case | Worst Case |
| add | O(1) | O(1) |
| del | O(1) | O(1) |
| x in s | O(1) | O(n) |
| Union s|t | O(len(s)+len(t)) | |
| Intersection s&t | O(min(len(s), len(t)) (replace "min" with "max" if t is not a set) | O(len(s) * len(t)) |
| Multiple intersection s1&s2&..&sn | (n-1)*O(l) where l is max(len(s1),..,len(sn)) | |
| Difference s-t | O(len(s)) | |
| s.difference_update(t) | O(len(t)) | |
| Symmetric Difference s^t | O(len(s)) | O(len(s) * len(t)) |
| s.symmetric_difference_update(t) | O(len(t)) | O(len(t) * len(s)) |
Сложность s-t или s.difference(t) (set_difference()) и разницы вычисляемой на месте s.difference_update(t) (set_difference_update_internal()) различна! Первый — O(len(s)) (для каждого элемента в s добавить его в новый набор, если он не в t). Второй — O(len(t)) (для каждого элемента t удалить его из s). Таким образом, необходимо подумать о том, какой из них предпочтительнее, в зависимости от того, какой из наборов является самым длинным и нужен ли новый набор.
Для выполнения операций над множествами, таких как s-t, и s, и t должны быть множествами. Однако можно реализовать и эквивалент, даже если t является любым итерируемым объектом, например, s.difference(l), где l — список.
Dict
Среднее время обработки, указанное для объектов dict, предполагает, что хеш-функция для объектов достаточно надежна, чтобы избежать коллизий. Средний случай предполагает, что ключи, используемые в параметрах, выбираются случайным образом из набора всех ключей.
Обратите внимание, что существует быстрый путь для словарей, который (на практике) работает только с ключами str; это не влияет на алгоритмическую сложность, но может значительно повлиять на константы: как быстро фактически завершается программа
| Operation | Average Case | Amortized Worst Case |
| k in d | O(1) | O(n) |
| Copy[3] | O(n) | O(n) |
| Get Item | O(1) | O(n) |
| Set Item[1] | O(1) | O(n) |
| Delete Item | O(1) | O(n) |
| Iteration[3] | O(n) | O(n) |
[1] - Эти операции основаны на «амортизированной» части «наихудшего случая». Отдельные действия могут занять гораздо больше времени, в зависимости от истории контейнера.
[2] - Извлечение промежуточного элемента с индексом k из списка размера n смещает все элементы после k на один слот влево с помощью memmove. n - k элементов должны быть перемещены, поэтому O(n-k). В лучшем случае извлекается предпоследний элемент, что требует одного шага, в худшем случае извлекается первый элемент, для чего требуется n-1 шагов. Средний случай для среднего значения k — выталкивание элемента из середины списка, для чего требуется O(n/2) = O(n) операций.
[3] - Для этих операций наихудший случай n — это максимальный размер контейнера, когда-либо достигнутый, а не только текущий размер. Например, если в словарь добавляются N объектов, то N-1 удаляются, словарь по-прежнему будет рассчитан на N объектов (как минимум) до тех пор, пока не будет сделана другая вставка.
Смотри еще: