Что такое сложность по времени для алгоритма на примере O(n)

Сложность по времени (Time Complexity) — это мера того, как время выполнения алгоритма растёт с увеличением размера входных данных. Обозначается с помощью "O-нотации" (Big-O notation), которая показывает верхнюю границу роста.

O(n) — линейная сложность. Время выполнения растёт прямо пропорционально размеру входных данных (n).

Пример:

def linear_search(arr, target):
    for element in arr:  # Проходим по каждому элементу (n итераций)
        if element == target:
            return True
    return False

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

Другие примеры:

• O(1) — константное время (доступ к элементу массива по индексу).
• O(n²) — квадратичная сложность (вложенные циклы).
• O(log n) — логарифмическая (бинарный поиск).

Чем меньше O, тем эффективнее алгоритм на больших данных.