Сложность операций встроенных типов

⏱ 35 мин · 🧩 заданий: 5

Почему это важно

Одна и та же задача может решаться за миллисекунды или за минуты — в зависимости от выбранной структуры данных. На собеседовании после решения всегда спрашивают: «Какая сложность?»

import time

n = 20_000
data_list = list(range(n))
data_set = set(data_list)
queries = range(n - 2_000, n)                  # 2000 поисков элементов в конце

start = time.perf_counter()
found = sum(1 for q in queries if q in data_list)      # O(n) на каждый поиск
t_list = time.perf_counter() - start

start = time.perf_counter()
found = sum(1 for q in queries if q in data_set)       # O(1) на каждый поиск
t_set = time.perf_counter() - start

print(f"list: {t_list * 1000:.1f} мс, set: {t_set * 1000:.3f} мс, в {t_list / t_set:.0f} раз быстрее")

list — динамический массив

Список хранит массив указателей на объекты подряд в памяти, с запасом свободного места.

lst = [10, 20, 30] ┌────┬────┬────┬────┬────┐ │ * │ * │ * │ │ │ ← size=3, allocated=5 └─┬──┴─┬──┴─┬──┴────┴────┘ 10 20 30 (объекты в куче)

Доступ по индексу — O(1): адрес вычисляется арифметикой.
append — в свободную ячейку O(1); если места нет — выделить больший массив и скопировать (редко) → амортизированная O(1).
insert(0, x), pop(0), del lst[0] — сдвиг всех элементов → O(n).
x in lst, lst.index(x), lst.count(x), lst.remove(x) — линейный перебор → O(n).

import sys

lst = []
prev = sys.getsizeof(lst)
for i in range(40):
    lst.append(i)
    size = sys.getsizeof(lst)
    if size != prev:                       # момент перевыделения
        print(f"len={len(lst):2}  размер={size} байт")
        prev = size

dict и set — хеш-таблицы

d[key] вычисляет hash(key), по нему находит ячейку таблицы и сравнивает ключ. В среднем O(1) независимо от размера. Таблица заполнена не более чем на ⅔ — при росте она перестраивается (амортизированно O(1)).

Наихудший случай — O(n), если много ключей с одинаковым хешем:

import time

class BadKey:
    def __init__(self, v):
        self.v = v
    def __hash__(self):
        return 42                          # все ключи в одну «корзину»
    def __eq__(self, other):
        return self.v == other.v

class GoodKey(BadKey):
    def __hash__(self):
        return hash(self.v)

for cls in (GoodKey, BadKey):
    start = time.perf_counter()
    d = {cls(i): i for i in range(1500)}
    print(f"{cls.__name__}: {(time.perf_counter() - start) * 1000:.1f} мс")

Словари в Python 3.7+ сохраняют порядок вставки (компактная таблица: массив индексов + массив записей).

Таблица сложностей

list

Операция	Средняя	Комментарий
`lst[i]`, `lst[i] = x`, `len(lst)`	O(1)
`lst.append(x)`, `lst.pop()`	O(1)*	*амортизированно
`lst.insert(i, x)`, `lst.pop(i)`, `del lst[i]`	O(n)	сдвиг хвоста
`x in lst`, `index`, `count`, `remove`	O(n)	перебор
`lst[a:b]`	O(b−a)	копия среза
`lst.extend(other)`	O(k)	k — длина other
`lst.sort()`, `sorted(lst)`	O(n log n)	Timsort
`min`, `max`, `sum`	O(n)
`lst * k`, `lst + other`	O(n·k), O(n+m)	новая копия

dict / set

Операция	Средняя	Худшая
`d[k]`, `d[k] = v`, `del d[k]`, `k in d`	O(1)	O(n)
`x in s`, `s.add(x)`, `s.discard(x)`	O(1)	O(n)
итерация	O(n)
`s \| t`, `s & t`, `s - t`	O(len(s)+len(t)), O(min), O(len(s))
`d.copy()`, `set(lst)`, `dict(pairs)`	O(n)

deque, heapq, str

Операция	Сложность
`dq.append`, `dq.appendleft`, `dq.pop`, `dq.popleft`	O(1)
`dq[i]` (в середине)	O(n)
`heapq.heappush`, `heappop`	O(log n)
`heapq.heapify`	O(n)
`s[i]`, `len(s)`	O(1)
`sub in s`, `s.find(sub)`, `s.replace`	O(n) (в среднем)
`s + t`	O(len(s) + len(t)) — новая строка
`"".join(parts)`	O(общей длины)

Типичные ошибки производительности

import time
from collections import deque

def timeit(label, func):
    start = time.perf_counter()
    func()
    print(f"{label:38} {(time.perf_counter() - start) * 1000:7.1f} мс")

N = 20_000

def queue_list():
    q = list(range(N))
    while q:
        q.pop(0)                    # ✗ O(n) на каждый pop → O(n²)

def queue_deque():
    q = deque(range(N))
    while q:
        q.popleft()                 # ✓ O(1)

def strings_plus():
    s = ""
    for i in range(N):
        s = s + str(i)              # ✗ потенциально O(n²) копирований

def strings_join():
    s = "".join(str(i) for i in range(N))   # ✓ O(n)

def dedupe_list():
    seen, out = [], []
    for x in range(N // 4):
        if x not in seen:           # ✗ поиск в списке
            seen.append(x); out.append(x)

def dedupe_set():
    seen, out = set(), []
    for x in range(N // 4):
        if x not in seen:           # ✓ поиск в множестве
            seen.add(x); out.append(x)

timeit("очередь на list.pop(0)", queue_list)
timeit("очередь на deque.popleft()", queue_deque)
timeit("строка через +", strings_plus)
timeit("строка через join", strings_join)
timeit("уникальные через список", dedupe_list)
timeit("уникальные через множество", dedupe_set)

Почему s = s + ... иногда быстрый

CPython оптимизирует s += t, если на строку нет других ссылок, и расширяет её на месте. Но это деталь реализации: в PyPy, при наличии второй ссылки или в выражении s = t + s оптимизация не работает. Идиоматично — "".join(...).

Ещё частые ошибки:

sorted() или max() внутри цикла по тем же данным → вынести из цикла;
list(d.keys()) и поиск в нём вместо key in d;
повторные вычисления одного и того же → кешировать (dict, functools.cache);
for i in range(len(lst)): if lst[i] in other_list → множество + enumerate.

Вопрос на собеседовании

«Почему поиск в множестве быстрее, чем в списке?» — Множество — хеш-таблица: по хешу элемента сразу вычисляется ячейка, поэтому поиск в среднем O(1). Список ищет перебором — O(n). Платим памятью и требованием хешируемости элементов.

Итог

list — динамический массив: индекс и append — O(1), вставка в начало и поиск — O(n).
dict/set — хеш-таблицы: поиск, вставка, удаление — O(1) в среднем, O(n) при коллизиях.
deque — O(1) с обоих концов; heapq — O(log n); str неизменяемая.
Ищете в цикле — используйте множество; очередь — deque; склейка строк — join.

Войдите, чтобы отмечать пройденные уроки.