Какая сложность операции `x in lst` для list, set, dict? Что выбрать для поиска по 1М элементов?

Варианты ответа

• list — O(n) линейный поиск, set/dict — O(1) average через хеш-таблицу. Для 1М элементов set даст разницу в 1000+ раз. Но set требует hashable элементов и не поддерживает индексацию
• list — O(log n) благодаря binary search, set — O(1), dict — O(n) из-за hash collision. Set оптимален для маленьких коллекций до 10K элементов, дальше — list с binary search
• Все три — O(1) благодаря оптимизациям CPython 3.10+. Для in-операции выбор контейнера не важен, можно использовать любой. Главное — память: list занимает меньше всего
• list — O(n²) из-за внутренней организации, set/dict — O(n log n) через B-tree. Для миллиона записей нужен dict, потому что у него быстрее iteration через keys()

Разбор ответа

Получить доступ к ответам — все вопросы →

Похожие вопросы из категории «Python»

• Чем отличаются списки и кортежи в Python?
• Как работает list comprehension и чем лучше цикла?
• Что такое генератор и чем он отличается от списка?
• Как работает менеджер контекста и зачем нужен?
• Объясните разницу между deepcopy и copy.