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

Временная сложность операции поиска элемента в массиве зависит от способа поиска и структуры данных.

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

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

def linear_search(arr, target):
    for i, value in enumerate(arr):
        if value == target:
            return i
    return -1

Этот алгоритм в худшем случае проверит все элементы, поэтому O(n).

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