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

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

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

Пример:

# O(n) – линейная сложность
def sum_list(lst):
    total = 0
    for num in lst:  # n операций
        total += num
    return total

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