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

Короткий ответ

В Python сложность операций зависит от типа коллекции. Для list: поиск по значению - O(n), доступ по индексу - O(1), добавление в конец - амортизированно O(1), вставка в середину - O(n). Для set и dict: поиск, добавление и удаление - в среднем O(1), в худшем случае O(n) при коллизиях хешей. Это достигается за счёт хеш-таблиц, но требует, чтобы ключи были хешируемыми и неизменяемыми.

Подробное объяснение

list - динамический массив. Доступ по индексу - O(1), так как элементы хранятся в непрерывной памяти. Поиск по значению требует линейного прохода - O(n). Добавление в конец через append - амортизированно O(1): при переполнении массив пересоздаётся с запасом, что даёт среднюю константную стоимость. Вставка в начало или середину (insert) сдвигает все последующие элементы - O(n). Удаление из конца - O(1), из середины - O(n).

set и dict - хеш-таблицы. Ключ (или элемент) преобразуется в хеш, который определяет индекс в массиве. Средняя сложность поиска, вставки и удаления - O(1). Однако при большом количестве коллизий (когда разные ключи дают одинаковый хеш) цепочки в корзинах растут, и сложность деградирует до O(n) в худшем случае. Python автоматически увеличивает таблицу при заполнении, чтобы поддерживать низкую плотность коллизий.

Важное отличие: dict хранит пары ключ-значение, set - только ключи. Оба требуют хешируемости элементов. Для dict ключи должны быть неизменяемыми (строки, числа, кортежи), для set - те же ограничения.

На практике

• Для list поиск по значению - это in оператор или .index(), оба O(n). Если нужен частый поиск - лучше использовать set.
• Для set и dict операции в среднем константны, но стоит помнить о памяти: хеш-таблицы занимают больше места, чем списки.
• При работе с большими данными важно, что dict и set требуют хешируемых ключей. Если ключ - изменяемый объект (например, список), это вызовет TypeError.
• Амортизированная сложность append для list означает, что редкие операции пересоздания массива "размазываются" по всем операциям, давая среднюю O(1).
• Для dict вставка нового ключа может вызвать resize таблицы - это редкая операция O(n), но в среднем вставка остаётся O(1).

Пример кода

PYTHON
import timeit

# list: поиск O(n)
lst = list(range(100000))
timeit.timeit(lambda: 99999 in lst, number=1000)  # ~0.05s

# set: поиск O(1)
st = set(range(100000))
timeit.timeit(lambda: 99999 in st, number=1000)  # ~0.0001s

# dict: вставка O(1) в среднем
d = {}
for i in range(100000):
    d[i] = i

Как отвечать на собеседовании

Начните с краткого ответа, затем уточните детали. Скажите, что для list доступ по индексу - O(1), поиск - O(n), вставка в конец - амортизированно O(1). Для set и dict - средняя O(1) для всех операций, худший случай O(n) при коллизиях. Упомяните, что это достигается хеш-таблицами, и что ключи должны быть хешируемыми. Если спросят про память - отметьте, что хеш-таблицы потребляют больше памяти, чем списки. Хорошо показать понимание амортизированной сложности и trade-off между временем и памятью.

Что проверяет интервьюер

Интервьюер оценивает:

• понимание внутреннего устройства коллекций, а не только заученные цифры;
• знание амортизированной сложности и её смысла;
• понимание требований к ключам (хешируемость, неизменяемость);
• умение объяснить, когда какую коллекцию выбрать;
• способность рассуждать о worst case и коллизиях.

Типичные ошибки

• Утверждение, что list.append всегда O(1) - забывают про амортизацию.
• Путаница между set и dict - говорят, что set хранит пары.
• Игнорирование худшего случая O(n) для хеш-таблиц.
• Утверждение, что list поиск - O(1) (путают с доступом по индексу).
• Забывают, что ключи dict должны быть неизменяемыми - это частая ошибка на практике.
• Не упоминают, что in для list - это O(n), а для set - O(1).