Какова временная сложность алгоритма линейного поиска элемента в словаре?

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

Однако, если говорить о линейном поиске (например, переборе всех элементов словаря для поиска по значению или по условию), то временная сложность будет O(n), где n — количество элементов в словаре.

Пример линейного поиска значения в словаре:

my_dict = {'a': 1, 'b': 2, 'c': 3}

# Поиск ключа по значению 2
for key, value in my_dict.items():
    if value == 2:
        print(f'Найден ключ: {key}')
        break

Здесь перебор всех элементов — линейная операция.