Подсчёт операций — основной способ оценить сложность алгоритма, не запуская код. Важны не секунды, а то, как растёт число базовых операций при росте размера входа n. Зная несколько простых правил, Big-O большинства функций можно определить за секунды.

Основная идея: отбрасываем константы

Присваивание, сравнение, арифметика, доступ по индексу считаются O(1). Постоянные множители и слагаемые низшего порядка отбрасываем: 3n + 7 — это O(n), а n^2/2 + 5n — это O(n^2).

Три правила подсчёта: последовательные блоки складываются, вложенные циклы умножаются, зависимые границы дают треугольник
Три правила подсчёта: последовательные блоки складываются, вложенные циклы умножаются, зависимые границы дают треугольник

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

Части, идущие одна за другой, дают сумму стоимостей, а в ответе остаётся наибольшая. Цикл на n шагов, затем цикл на n * n шагов — это n + n^2, то есть O(n^2).

python
def steps_sequential(n):
    ops = 0
    for _ in range(n):
        ops += 1
    for _ in range(n):
        for _ in range(n):
            ops += 1
    return ops

for n in (10, 100, 1000):
    print(n, steps_sequential(n))