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

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

Но если искать значение (не ключ) перебором, сложность будет O(n), так как требуется проверить каждый элемент:

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

# Поиск значения перебором — O(n)
value_to_find = 2
for key, value in my_dict.items():
    if value == value_to_find:
        print(f"Found: {key}")
        break

Для частых поисков по значению лучше использовать структуры, оптимизированные для этого (например, два словаря или defaultdict).