Какова сложность поиска и добавления в коллекциях list, set, dict в Python?

Что проверяют

Умеете ли вы выбирать структуру под операцию, а не только помнить таблицу сложностей. Типичное продолжение: интервьюер показывает цикл с if x in items и спрашивает, как его ускорить, или просит сделать очередь.

Как отвечать

Сводка для CPython:

• list, поиск: x in lst и lst.index(x) проходят по элементам, O(n). Доступ по индексу lst[i] O(1), внутри массив указателей;
• list, добавление: append амортизированно O(1), список выделяет память с запасом. insert(i, x) O(n) из-за сдвига хвоста, дороже всего insert(0, x) и pop(0);
• set, поиск и добавление: x in s и s.add(x) O(1) в среднем, O(n) в худшем при массовых коллизиях хэшей;
• dict, поиск и добавление по ключу: k in d, d[k] и d[k] = v O(1) в среднем. Но v in d.values() это уже перебор за O(n).

За константу у set и dict платят памятью: хэш-таблица держит свободные слоты и хранит хэши, поэтому множество заметно тяжелее списка той же длины. Элементы должны быть хэшируемыми. Порядок вставки сохраняет dict, а set порядок не гарантирует.

Практические выводы, которые стоит озвучить:

• много проверок по одной коллекции: один раз построить set(items) за O(n), дальше каждая проверка O(1);
• очередь: collections.deque, у него append, appendleft и popleft работают за O(1);
• отсортированный список: поиск через bisect за O(log n), но вставка insort всё равно O(n) из-за сдвига.

Где спотыкаются

Пишут for x in a: if x in b по двум спискам и получают O(n·m). На десятках тысяч элементов это секунды вместо миллисекунд.

Строят set ради одной проверки. Построение само по себе O(n), выигрыша нет, а памяти ушло больше.

Делают очередь на list.pop(0). Каждое извлечение сдвигает весь список, и обработка большой очереди становится квадратичной.