Как определить временную сложность операции поиска элемента в списке?

Временная сложность поиска элемента в списке зависит от типа списка и способа поиска:

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

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

• Если нужна более быстрая проверка наличия элемента, лучше использовать множества (set) или словари (dict), где поиск по ключу выполняется за амортизированное O(1).

Пример линейного поиска:

my_list = [3, 5, 7, 9]
value = 7
found = value in my_list  # O(n)

Для бинарного поиска можно использовать модуль bisect, если список отсортирован:

import bisect
my_list = [1, 3, 5, 7, 9]
value = 7
index = bisect.bisect_left(my_list, value)
found = index < len(my_list) and my_list[index] == value  # O(log n)