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

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

Пример:

my_list = [1, 2, 3, 4, 5]
# Поиск элемента 3 — O(n)
if 3 in my_list:
    print("Found")

Для частых операций поиска лучше использовать множества (set) или словари (dict), где поиск происходит за O(1) в среднем случае благодаря хеш-таблицам.