Какая сложность у основных операций со списком, словарём и множеством?
- Big O для list и dict в Python
- Почему insert(0) у списка медленный?
- Что быстрее — проверка in для списка или для множества?
Список — массив: **доступ по индексу и append — O(1)**, вставка в начало и поиск in — O(n).
- dict и set — хеш-таблицы: поиск, вставка, удаление в среднем O(1)
- Нужна очередь с двух концов —
collections.deque:appendleft/popleftза O(1)
А ещё sort — O(n log n), x in list в цикле — частая причина O(n²)
Подробно
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)Что хотят услышать
- Список как массив: что быстро, что медленно, и почему.
- Средняя O(1) у dict/set с оговоркой про худший случай.
- Амортизированная сложность
append. - Практические замены:
setдля проверок,dequeдля очереди.
Частые ошибки
- Называть
listсвязным списком. - Говорить «словарь всегда O(1)» без слова «в среднем».
Проверьте себя
Один верный вариант. Подумайте, потом откройте ответ.
Показать варианты и ответ
- ✗Вставка в начало списка — O(1), как append, а поиск in в отсортированном списке — O(log n)
- ✓Индекс и append у списка — O(1), in — O(n); у dict и set поиск в среднем O(1)
- ✗Поиск x in list — O(1), x in set — O(n)
- ✗Сортировка списка — O(n)
Что спросят дальше
Разбор темы
- Память и производительность CPython
Подсчёт ссылок и сборщик циклов, слабые ссылки, интернирование чисел и строк, копирование, сложность операций, профилирование и способы ускорения.
Связанные вопросы
Разбор собеседования с sotto
После собеседования sotto разбирает разговор: оценка, каждый вопрос — хорошо, частично или слабо, чего не хватило в ответе и над чем поработать к следующему разу. Первые 30 минут бесплатно.