Что означает линейная сложность

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

Пример:

def linear_search(arr, target):
    for item in arr:  # O(n) - один цикл по всем элементам
        if item == target:
            return True
    return False

Характеристики:

• График - прямая линия
• Время выполнения: 1мс на 1000 элементов → ~10мс на 10000
• Типичные случаи: перебор массива, поиск в неотсортированном списке