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

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

Пример кода:

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

В этом примере:

• В лучшем случае (элемент первый) сложность O(1)
• В среднем и худшем случаях — O(n)

Пространственная сложность — O(1), так как алгоритм не использует дополнительной памяти.