Какая временная сложность доступа к элементу словаря по ключу в Python?

Средняя (амортизированная) сложность доступа по ключу — O(1). Это обеспечивается внутренней реализацией словаря как хеш-таблицы.

Как это работает:

1. Python вычисляет хеш ключа (например, строки 'b').
2. По этому хешу находится «корзина» (bucket), где хранится пара ключ-значение.
3. Если в корзине один элемент — доступ мгновенный.

Пример:

config = {'host': 'localhost', 'port': 8080, 'debug': True}
# Сложность ~O(1), не зависит от размера словаря
server_port = config['port']
print(server_port)  # 8080

Важные нюансы:

• Худший случай O(n) теоретически возможен при большом количестве коллизий хешей, но на практике, благодаря качественной хеш-функции и динамическому рехешированию, встречается крайне редко.
• Операции key in dict, dict.get(key), присваивание dict[key] = value также имеют среднюю сложность O(1).
• Ключ должен быть хешируемым объектом (неизменяемым типом: int, str, tuple).