Оценка сложности алгоритмов

Зачем O-большое

Время работы зависит от компьютера, языка, данных. Чтобы сравнивать алгоритмы, а не железо, смотрят, как растёт число операций при росте входа n.

O(f(n)) — верхняя оценка роста: «при больших n работа растёт не быстрее, чем f(n), с точностью до константы».

Правила:

• константы отбрасываются: O(3n + 10) → O(n);
• остаются старшие члены: O(n² + n) → O(n²);
• разные входы — разные буквы: два списка длины n и m → O(n + m) или O(n·m).

Классы сложности

import math

print(f"{'n':>8} {'log n':>7} {'n log n':>10} {'n²':>14} {'2ⁿ':>12}")
for n in [10, 100, 1_000, 10_000, 100_000]:
    two = f"{2**n:.1e}" if n <= 1000 else "∞"
    print(f"{n:>8} {math.log2(n):>7.1f} {n * math.log2(n):>10.0f} {n * n:>14} {two:>12}")

Как оценивать код

Последовательные блоки складываются

def f(nums):
    total = sum(nums)          # O(n)
    nums.sort()                # O(n log n)
    return nums[0], total      # O(1)
# итого O(n log n) — доминирует сортировка

Вложенные циклы перемножаются

def pairs(nums):
    result = []
    for i in range(len(nums)):          # n раз
        for j in range(i + 1, len(nums)):   # до n раз
            result.append((i, j))
    return result
# n·(n−1)/2 итераций → O(n²)

Скрытая сложность встроенных операций

for x in a:            # n раз
    if x in b:         # b — список: O(m) на каждую проверку!
        ...
# O(n·m), а с b = set(b) — O(n + m)

x in list, list.index, list.remove, list.insert(0, ...), срезы lst[1:], "".join внутри цикла, sorted внутри цикла — у всех линейная или большая цена.

Логарифм — когда задача делится пополам

def steps_halving(n):
    steps = 0
    while n > 1:
        n //= 2
        steps += 1
    return steps

for n in [8, 1_000, 1_000_000, 10**9]:
    print(n, "→", steps_halving(n), "шагов")

Рекурсия — дерево вызовов

calls = 0

def fib(n):
    global calls
    calls += 1
    return n if n < 2 else fib(n - 1) + fib(n - 2)

for n in [10, 15, 20, 25]:
    calls = 0
    fib(n)
    print(f"fib({n}): {calls} вызовов")      # растёт как ~1.6ⁿ → O(2ⁿ)

Каждый вызов порождает два — дерево глубины n, вызовов порядка 2ⁿ. С мемоизацией каждое значение считается один раз → O(n). Это и есть идея динамического программирования.

Амортизированная сложность

list.append иногда копирует весь массив (O(n)), но так редко, что в среднем на операцию — O(1). Так же устроены dict и set при росте.

Сложность по памяти

Считается дополнительная память, кроме входа:

def reverse_copy(nums):
    return nums[::-1]                   # O(n) памяти — новый список

def reverse_in_place(nums):
    i, j = 0, len(nums) - 1
    while i < j:                        # O(1) памяти — только два индекса
        nums[i], nums[j] = nums[j], nums[i]
        i, j = i + 1, j - 1

Рекурсия тратит память на стек: глубина d → O(d). В Python глубина ограничена (~1000, sys.getrecursionlimit()), поэтому глубокую рекурсию переписывают итеративно.

Ограничения → сложность

Примерно 10⁷–10⁸ простых операций в секунду на Python (реально — ближе к 10⁷). По ограничениям задачи можно угадать ожидаемое решение:

Как говорить о сложности на собеседовании

1. Сначала предложите простое решение и назовите его сложность: «перебор пар — O(n²) по времени, O(1) по памяти».
2. Найдите узкое место: «дорого искать дополнение — можно хранить увиденное в множестве».
3. Улучшите и снова оцените: «O(n) по времени, O(n) по памяти».
4. Обсудите компромисс время/память и крайние случаи.

Итог

• O-большое — скорость роста работы, константы и младшие члены отбрасываются.
• Последовательные шаги складываются, вложенные — перемножаются; не забывайте скрытую цену встроенных операций.
• Деление пополам → log n; рекурсия с ветвлением → экспонента (лечится мемоизацией).
• Память тоже считается, включая стек рекурсии.
• По ограничениям задачи можно понять, какая сложность нужна.