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

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

Основные виды сложности:

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

Пример:

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

# O(n²) – квадратичная сложность
def find_pairs(lst):
    pairs = []
    for i in lst:      # Внешний цикл → O(n)
        for j in lst:  # Вложенный цикл → O(n * n) = O(n²)
            pairs.append((i, j))
    return pairs

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