Список — массив: **доступ по индексу и append — O(1)**, вставка в начало и поиск in — O(n).
sottocollections.deque: appendleft/popleft за O(1)А ещё sort — O(n log n), x in list в цикле — частая причина O(n²)
Так подсказку видит пользователь sotto на живом собеседовании — за пару секунд, пока вы думаете вслух.
list — динамический массив ссылок:
| Операция | Сложность |
|---|---|
a[i], a[i] = x, len(a) | O(1) |
append, pop() с конца | O(1) амортизированно |
insert(0, x), pop(0), del a[i] | O(n) — элементы сдвигаются |
x in a, a.index(x), a.remove(x) | O(n) |
срез a[i:j] | O(j − i) |
sort | O(n log n) |
append амортизированно O(1): память выделяется с запасом, и редкие расширения размазываются по многим вставкам.
dict и set — хеш-таблицы: d[k], k in d, вставка, удаление — O(1) в среднем, O(n) в худшем случае при массовых коллизиях. Обход — O(n).
deque — двусторонняя очередь: добавление и удаление с обоих концов O(1), но доступ по индексу в середину — O(n).
Практический вывод: если в цикле проверяется x in big_list, получается O(n·m). Превратив список в set один раз, получаем O(n + m). Очередь на списке с pop(0) — O(n) на каждую операцию, на deque — O(1).
from collections import deque
ids = list(range(100_000))
lookups = range(0, 100_000, 7)
slow = [x for x in lookups if x in ids] # O(n·m)
ids_set = set(ids)
fast = [x for x in lookups if x in ids_set] # O(n + m)
queue = deque([1, 2, 3])
queue.appendleft(0) # O(1)
queue.popleft() # O(1); у списка pop(0) — O(n)append.set для проверок, deque для очереди.list связным списком.sotto слышит вопрос интервьюера и показывает короткий ответ и план, как в блоке «Коротко». Оставьте контакт — пришлём доступ и промокод.