Какая алгоритмическая сложность поиска в словаре в Python

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

Пример:

my_dict = {'a': 1, 'b': 2, 'c': 3}
# O(1) операция
value = my_dict['b']

Ключевые моменты:

• Хеш-функция вычисляет индекс корзины за константное время
• При отсутствии коллизий доступ к элементу мгновенный
• В CPython словарь автоматически масштабируется для минимизации коллизий