Как измеряется алгоритмическая сложность

Алгоритмическая сложность измеряется с помощью нотации Big-O (О-большое), которая описывает верхнюю границу роста времени выполнения или использования памяти алгоритма в зависимости от размера входных данных (n). Основные виды сложности:

• O(1) – константная (доступ по индексу в массиве)
• O(log n) – логарифмическая (бинарный поиск)
• O(n) – линейная (поиск в неотсортированном массиве)
• O(n log n) – линейно-логарифмическая (быстрая сортировка)
• O(n²) – квадратичная (пузырьковая сортировка)
• O(2ⁿ) – экспоненциальная (рекурсивное вычисление чисел Фибоначчи)

Пример:

# O(n) - линейная сложность
def linear_search(arr, target):
    for item in arr:
        if item == target:
            return True
    return False

Сложность анализируется для худшего случая, игнорируя константы и меньшие члены (O(2n + 5) → O(n)).