Какая временная сложность получения элемента из словаря (dict) в Python?

Средняя (амортизированная) временная сложность операции dict[key] — O(1). Это основное преимущество словарей, делающее их идеальными для быстрого поиска и ассоциативного хранения данных.

Практический пример:

# Время доступа к элементу в словаре из 10 и 1_000_000 элементов ~одинаково.
small_dict = {'a': 1, 'b': 2}
large_dict = {i: i*2 for i in range(1_000_000)}

value_small = small_dict['b']   # ~O(1)
value_large = large_dict[999999] # ~O(1), почти так же быстро

Объяснение "почему O(1)": Внутри словарь — это хеш-таблица. При обращении dict[key]:

1. Вычисляется hash(key).
2. Используя этот хеш, находится нужная «корзина» памяти.
3. Из корзины извлекается значение. Это операция с фиксированной стоимостью, не требующая обхода всех элементов.

Связанные операции с той же сложностью O(1):

• dict.get(key)
• key in dict (проверка наличия ключа)
• dict[key] = value (присваивание)
• del dict[key] (удаление)