Ответ
Временная сложность получения значения по ключу в словаре Python (dict) в среднем составляет O(1) (константное время).
Почему O(1)?
Словари в Python реализованы на основе хеш-таблицы. Когда вы запрашиваете my_dict[key], происходит следующее:
- Вычисляется хеш от ключа
hash(key). Эта операция занимает константное время. - По значению хеша определяется индекс в нижележащем массиве (массиве "корзин"), где должно храниться значение.
- Происходит доступ к элементу по этому индексу.
Все эти шаги в среднем выполняются за постоянное время, не зависящее от количества элементов в словаре.
Худший случай:
В редких случаях, когда возникает множество коллизий (разные ключи дают одинаковый хеш), сложность может деградировать до O(n). В этой ситуации для нахождения нужного элемента приходится перебирать все ключи, попавшие в одну "корзину". Однако благодаря качественным хеш-функциям и механизму изменения размера таблицы на практике это почти не встречается.
Требование к ключам:
Ключи словаря должны быть хешируемыми, то есть иметь неизменяемое значение в течение всего своего жизненного цикла (например, int, str, tuple).