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

Сложность операций зависит от реализации коллекции.

list (динамический массив):

• Поиск по индексу: O(1) - прямой доступ.
• Поиск по значению (in, index): O(n) - линейный проход.
• Добавление в конец (append): амортизированная O(1) - в среднем, но при переполнении массива O(n).
• Добавление в начало/середину (insert): O(n) - сдвиг элементов.

set (хэш-таблица):

• Поиск (in, contains): O(1) в среднем, O(n) в худшем случае (коллизии).
• Добавление (add): O(1) в среднем, O(n) в худшем случае.

dict (хэш-таблица):

• Поиск по ключу (get, in): O(1) в среднем, O(n) в худшем случае.
• Добавление/обновление: O(1) в среднем, O(n) в худшем случае.

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