Анализ алгоритмов: асимптотика, инварианты и доказательство корректности

Есть два вопроса, которые нужно задать любому куску кода, прежде чем выпускать его в прод: он вообще правильный? и что с ним будет, когда данных станет в тысячу раз больше?

Первый вопрос — про корректность, второй — про сложность. Оба звучат как «академическая теория», и оба на самом деле про деньги: инцидент в три часа ночи почти всегда оказывается либо нарушенным инвариантом («здесь не могло быть null, но оно есть»), либо квадратичной асимптотикой, которая мирно спала, пока таблица не выросла с 10 тысяч строк до миллиона.

Эта статья — фундамент всего трека. Дальше, разбирая сортировки, графы и динамическое программирование, мы будем постоянно пользоваться словарём отсюда: O, Θ, инвариант, рекуррентность, амортизация, нижняя оценка. Карта трека — в статье Алгоритмы: карта трека.

1. Зачем нужна абстракция: почему нельзя просто замерить время

Наивный ответ на «какой алгоритм быстрее» — запустить оба и посмотреть на секундомер. Проблема в том, что секундомер меряет не алгоритм, а конкретный запуск конкретной реализации на конкретном железе с конкретными данными. Поменяйте хоть один из четырёх факторов — и результат может перевернуться:

• другой процессор, другой размер L2-кэша, другая частота памяти;
• другой язык и рантайм: Python против C — разница в 50–100 раз на том же алгоритме;
• другой компилятор и флаги оптимизации;
• другие входные данные: почти отсортированный массив против случайного.

Нам нужна характеристика, которая описывает сам алгоритм и переживает смену железа. Такой характеристикой стала функция роста: как меняется число элементарных операций при росте размера входа n. Константы при этом отбрасываются — не потому, что они не важны (они важны, к этому вернёмся в разделе 9), а потому, что они и есть та часть, которая зависит от железа и реализации.

Модель вычислений: RAM

Чтобы «число операций» было определено, нужна модель машины. Классическая — RAM (Random Access Machine): память — массив ячеек с доступом за константу, элементарные операции (сложение, сравнение, присваивание, обращение по индексу) стоят единицу, машинное слово вмещает индекс входа (обычно O(log n) бит).

Модель — это соглашение, и у него есть цена. RAM врёт в трёх местах, о которых стоит помнить с самого начала:

1. Доступ к памяти не константный. L1-кэш ~1 нс, RAM ~100 нс, SSD ~100 мкс. Отсюда практика, разобранная в Практической оптимизации и в алгоритмах внешней памяти.
2. Арифметика не всегда константная. Умножение 4096-битных чисел — не одна операция; в теории чисел это принципиально.
3. Параллелизм не учитывается — для него нужны свои модели (параллельные алгоритмы).

Пока держим в голове: асимптотика — первое приближение, очень полезное и иногда недостаточное.

2. Асимптотические обозначения строго

Интуитивно O — это «не хуже чем», Ω — «не лучше чем», Θ — «ровно такого порядка». Формально это множества функций.

Пусть f, g: ℕ → ℝ⁺.

• f(n) = O(g(n)) ⟺ существуют c > 0 и n₀, такие что f(n) ≤ c·g(n) для всех n ≥ n₀. Верхняя оценка с точностью до константы, начиная с некоторого места.
• f(n) = Ω(g(n)) ⟺ существуют c > 0 и n₀: f(n) ≥ c·g(n) при n ≥ n₀. Нижняя оценка.
• f(n) = Θ(g(n)) ⟺ одновременно O и Ω. Точный порядок роста.
• f(n) = o(g(n)) ⟺ f(n)/g(n) → 0. Строго меньший порядок: n = o(n log n).
• f(n) = ω(g(n)) ⟺ f(n)/g(n) → ∞.

Аналогия: O — это ≤, Ω — ≥, Θ — =, o — <, ω — >, но в мире функций и с точностью до константного множителя.

Знак равенства здесь — исторический ляп: O(g) — это множество, и корректнее писать f ∈ O(g). Поэтому запись читается только слева направо: n = O(n²) верно, O(n²) = n бессмысленно.

Что чаще всего понимают неправильно

O — не «худший случай», а Θ — не «средний». Это ортогональные измерения. Сначала вы фиксируете сценарий (худший / средний / лучший вход), получаете функцию, и только потом описываете её рост через O/Θ. Совершенно законно сказать: «время работы quicksort в худшем случае Θ(n²), а математическое ожидание при случайном пивоте Θ(n log n)».

O(n²) — корректная (хоть и слабая) оценка для сортировки слиянием. O — верхняя граница, никто не обещал её точность. Если вы знаете точный порядок — говорите Θ, это информативнее. В индустрии O почти всегда употребляют в смысле Θ для худшего случая; это удобная небрежность, но на собеседовании или в статье лучше быть точным.

Асимптотика ничего не говорит про малые n. Θ(n log n)-алгоритм с константой 1000 проиграет Θ(n²) с константой 1 на всех n < ~14000.

Иерархия роста

Полезно помнить порядок «по нарастающей»:

Θ(1) ≺ Θ(α(n)) ≺ Θ(log log n) ≺ Θ(log n) ≺ Θ(log²n) ≺ Θ(√n) ≺ Θ(n)
     ≺ Θ(n log n) ≺ Θ(n²) ≺ Θ(n³) ≺ Θ(2ⁿ) ≺ Θ(n!) ≺ Θ(nⁿ)

Здесь α(n) — обратная функция Аккермана, растущая настолько медленно, что для любых реальных n она ≤ 4; она возникает в анализе СНМ (система непересекающихся множеств), см. структуры данных.

Практическое правило порядков для одной секунды на типичном CPU (условно, 10⁸–10⁹ простых операций):

Эту таблицу стоит выучить: она за пять секунд отвечает на вопрос «зайдёт ли решение» и на продовый вопрос «выдержим ли мы рост нагрузки в 10 раз».

Немного истории

Статья Кнута, где он навёл порядок с Ω и Θ, — «Big Omicron and Big Omega and Big Theta», SIGACT News, 1976: dl.acm.org/doi/10.1145/1008328.1008329.

3. Как считать сложность кода

Базовые правила сложения и умножения:

• последовательные блоки — максимум: O(f) + O(g) = O(max(f, g));
• вложенные циклы — произведение;
• константный множитель отбрасывается, младшие члены поглощаются.

Разберём типичные шаблоны.

# 1) Θ(n) — один линейный проход
total = 0
for x in data:            # n итераций, тело Θ(1)
    total += x

# 2) Θ(n²) — вложенный цикл по всем парам
for i in range(n):
    for j in range(n):
        check(i, j)

# 3) Θ(n²), а не Θ(n log n): треугольный цикл
for i in range(n):
    for j in range(i, n):  # n + (n-1) + ... + 1 = n(n+1)/2 итераций
        check(i, j)

# 4) Θ(log n) — параметр делится, а не уменьшается
while lo < hi:
    mid = (lo + hi) // 2
    ...

# 5) Θ(n log n) — внешний линейный, внутренний логарифмический
for i in range(n):
    j = 1
    while j < n:
        j *= 2

Главная ловушка новичков — скрытая сложность вызываемых функций. В Python это особенно больно:

# Выглядит как Θ(n), на деле Θ(n²):
result = ""
for chunk in chunks:      # n итераций
    result += chunk       # копирование всей строки: Θ(len(result))

# Правильно — Θ(n):
result = "".join(chunks)

# Ещё пример: `x in lst` — это Θ(n), `x in set` — Θ(1) в среднем
seen = []
for x in data:
    if x in seen:         # линейный поиск внутри цикла → Θ(n²)
        ...
    seen.append(x)

Справочник по стоимости операций CPython — обязателен к прочтению: wiki.python.org/moin/TimeComplexity. Аналоги есть для любого языка: сложность контейнеров в cppreference, Big-O коллекций Java в javadoc, документация к Go-слайсам и мапам (Go overview).

Общая методика анализа:

4. Рекуррентности: дерево рекурсии и мастер-теорема

Для рекурсивных алгоритмов время описывается рекуррентным соотношением. Классика «разделяй и властвуй» (подробнее — в статье о рекурсии):

T(n) = a · T(n/b) + f(n)

где a — число подзадач, n/b — их размер, f(n) — стоимость разбиения и слияния.

Самый наглядный способ — дерево рекурсии: нарисовать работу на каждом уровне и сложить.

Мастер-теорема (CLRS, гл. 4)

Сравниваем f(n) с «весом листьев» n^(log_b a):

1. Листья доминируют. Если f(n) = O(n^(log_b a − ε)) для некоторого ε > 0, то T(n) = Θ(n^(log_b a)).
2. Баланс. Если f(n) = Θ(n^(log_b a) · log^k n), k ≥ 0, то T(n) = Θ(n^(log_b a) · log^(k+1) n).
3. Корень доминирует. Если f(n) = Ω(n^(log_b a + ε)) и выполняется условие регулярности a·f(n/b) ≤ c·f(n) при c < 1, то T(n) = Θ(f(n)).

Разбор примеров:

Последняя строка важна: мастер-теорема работает только для деления в разы, а не вычитания. Для T(n) = T(n−1) + f(n) просто суммируйте: T(n) = Σ f(i).

Есть и случаи «между» — когда f(n) меньше n^(log_b a), но не полиномиально меньше (например, f(n) = n/log n); мастер-теорема их не покрывает. Тогда — метод подстановки или теорема Акра–Бацци, которая ещё и допускает неравные размеры подзадач (T(n) = T(n/3) + T(2n/3) + n — рекуррентность для медианы медиан и для несбалансированного quicksort, ответ Θ(n log n)).

Метод подстановки: угадать и доказать индукцией

Докажем, что T(n) = 2T(⌊n/2⌋) + n ≤ c·n·log₂n для подходящего c.

База:      n = 2:   T(2) = 2T(1) + 2 = 4 ≤ c·2·1 при c ≥ 2.
Переход:   предположим T(k) ≤ c·k·log₂k для всех k < n. Тогда
           T(n) ≤ 2·c·(n/2)·log₂(n/2) + n
                = c·n·(log₂n − 1) + n
                = c·n·log₂n − c·n + n
                ≤ c·n·log₂n            (при c ≥ 1)

Обратите внимание на технику: индукционная гипотеза должна быть достаточно сильной. Попытка доказать T(n) ≤ c·n провалится, и это само по себе сигнал, что оценка неверна.

5. Амортизационный анализ

Иногда «худший случай одной операции» — обманчиво пессимистичная метрика. Классика — push в динамический массив (list в Python, vector в C++, слайс в Go): обычно это Θ(1), но при переполнении ёмкости нужно выделить новый буфер вдвое больше и скопировать всё содержимое — Θ(n).

Значит ли это, что n вызовов push стоят Θ(n²)? Нет: дорогие операции редки.

Три стандартных метода (Tarjan, «Amortized Computational Complexity», 1985 — epubs.siam.org/doi/10.1137/0606031):

1. Агрегатный метод. Считаем суммарную стоимость n операций и делим на n. Копирования происходят при размерах 1, 2, 4, …, 2^k ≤ n, суммарно 1 + 2 + 4 + … + n < 2n копирований. Плюс n дешёвых вставок → < 3n операций всего, то есть Θ(1) амортизированно.

2. Бухгалтерский метод (accounting). Назначаем каждой операции «цену» 3 условные единицы: 1 тратим на саму вставку, 2 кладём «в банк» на счёт элемента. Когда наступает удвоение, в банке накоплено ровно столько, чтобы оплатить копирование всех элементов. Инвариант: баланс банка никогда не отрицателен.

3. Метод потенциалов. Вводим функцию Φ(D) — «запасённую энергию» структуры. Амортизированная стоимость: ĉᵢ = cᵢ + Φ(Dᵢ) − Φ(Dᵢ₋₁). Тогда Σĉᵢ = Σcᵢ + Φ(Dₙ) − Φ(D₀) ≥ Σcᵢ, если Φ(Dₙ) ≥ Φ(D₀) — то есть сумма амортизированных стоимостей ограничивает сверху реальную.

Для динамического массива берём Φ = 2·len − cap:

• обычная вставка: c = 1, ΔΦ = 2 → ĉ = 3;
• вставка с удвоением при len = cap = k: c = k + 1, до операции Φ = 2k − k = k, после Φ = 2(k+1) − 2k = 2 → ĉ = (k+1) + 2 − k = 3.

Ровно 3 в обоих случаях. Красиво и, что важнее, механически проверяемо.

Практические следствия

• Коэффициент роста имеет значение. Рост в 2 раза даёт ĉ = 3; рост в 1.5 раза — ĉ ≈ 4, но лучше переиспользует освобождённую память (сумма предыдущих блоков может покрыть следующий запрос). Поэтому в std::vector GCC/Clang коэффициент 2, а в MSVC и в Vec Rust — компромиссы; Python CPython наращивает примерно на 12.5% (list_resize в listobject.c).
• Амортизация ≠ гарантия по латентности. Если у вас p99-SLA 10 мс, а одна операция из миллиона занимает 200 мс из-за рехеширования, «амортизированно O(1)» вас не спасёт. Real-time системы используют инкрементальные структуры, которые размазывают переезд по многим операциям. Тот же вопрос — про stop-the-world паузы GC.
• Амортизация ломается при откате. Если после каждого дорогого удвоения делать pop, который сжимает массив вдвое, вы получите чередование Θ(n)-операций. Поэтому реальные реализации сжимают только при заполнении ниже 1/4, а не 1/2 — создают гистерезис.

6. Корректность: инварианты цикла

Тесты показывают наличие ошибок, а не их отсутствие (Дейкстра). Доказательство — показывает отсутствие. На практике вам не нужно формально верифицировать каждую функцию, но уметь формулировать инвариант нужно постоянно: это то, что превращает «вроде работает» в «работает, и я знаю почему».

Классическая схема доказательства цикла состоит из трёх шагов (CLRS, гл. 2):

Это индукция, замаскированная под цикл: инициализация — база, сохранение — переход, завершение — извлечение вывода.

Пример 1: сортировка вставками

def insertion_sort(a: list[int]) -> None:
    """Сортировка вставками. Время: O(n²) худший/средний, O(n) на почти
    отсортированных данных. Память: O(1) дополнительно, in-place, стабильная."""
    for i in range(1, len(a)):
        # ИНВАРИАНТ: подмассив a[0..i-1] содержит те же элементы,
        # что были в нём изначально, но в отсортированном порядке.
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key

• Инициализация. i = 1: подмассив a[0..0] из одного элемента тривиально отсортирован, элементы те же.
• Сохранение. Внутренний цикл сдвигает вправо все элементы, строго большие key, и вставляет key на освободившееся место. Порядок среди сдвинутых сохранён, key оказался правее всех ≤ key и левее всех > key → a[0..i] отсортирован.
• Завершение. Цикл кончается при i = n, инвариант даёт: a[0..n-1] отсортирован и содержит исходные элементы. Это ровно определение корректной сортировки.

Обратите внимание: инвариант говорит про два свойства — упорядоченность и сохранение мультимножества элементов. Забыть второе — типичная ошибка: алгоритм, заполняющий массив нулями, «отсортирован», но неверен.

Пример 2: бинарный поиск и три способа ошибиться

def lower_bound(a: list[int], target: int) -> int:
    """Индекс первого элемента >= target (или len(a), если такого нет).
    Предусловие: a отсортирован по неубыванию.
    Время: O(log n). Память: O(1)."""
    lo, hi = 0, len(a)          # полуинтервал [lo, hi)
    # ИНВАРИАНТ: ответ лежит в [lo, hi];
    #   все a[k] <  target для k < lo
    #   все a[k] >= target для k >= hi
    while lo < hi:
        mid = lo + (hi - lo) // 2      # без переполнения; в Python не критично,
                                       # в C/C++/Java — обязательно
        if a[mid] < target:
            lo = mid + 1               # a[mid] точно левее ответа
        else:
            hi = mid                   # a[mid] — кандидат, но не отбрасываем его
    return lo                          # lo == hi, инвариант даёт ответ

Разбор по схеме:

• Инициализация. lo=0, hi=n: оба «все …»-условия пусты, значит истинны.
• Сохранение. Если a[mid] < target, то по отсортированности все a[k] < target при k ≤ mid, и сдвиг lo = mid+1 инвариант сохраняет. Иначе a[mid] ≥ target, и все a[k] ≥ target при k ≥ mid, сдвиг hi = mid корректен.
• Завершение. Нужен вариант — целочисленная мера, строго убывающая и ограниченная снизу. Здесь hi − lo: при lo < hi имеем lo ≤ mid < hi, значит ветка lo = mid+1 строго увеличивает lo, а hi = mid строго уменьшает hi. Мера убывает минимум на 1 и ≥ 0 → цикл завершается. При lo = hi инвариант даёт ровно определение lower_bound.

Три классические ошибки, которые доказательство ловит мгновенно:

1. mid = (lo + hi) // 2 переполняется в языках с 32-битным int. Знаменитая заметка Джошуа Блоха «Nearly All Binary Searches and Mergesorts are Broken» — баг прожил в JDK девять лет: research.google/blog/extra-extra-read-all-about-it….
2. hi = mid - 1 в полуинтервальной версии теряет ответ (инвариант «все a[k] ≥ target при k ≥ hi» ломается).
3. lo = mid вместо lo = mid + 1 не уменьшает вариант при hi = lo + 1 → бесконечный цикл. Именно поэтому вариант нужно выписывать отдельно: инвариант отвечает за «правильно», вариант — за «когда-нибудь закончится».

Формальная база всего этого — тройки Хоара {P} S {Q} из статьи 1969 года «An Axiomatic Basis for Computer Programming»: dl.acm.org/doi/10.1145/363235.363259. Правило для цикла: если {I ∧ B} S {I}, то {I} while B do S {I ∧ ¬B}.

Индукция для рекурсии

Для рекурсивных функций схема иная: сильная индукция по размеру входа.

def merge_sort(a: list[int]) -> list[int]:
    """Сортировка слиянием. Время: Θ(n log n) всегда. Память: Θ(n)."""
    if len(a) <= 1:
        return a                              # БАЗА: список длины 0 или 1 отсортирован
    mid = len(a) // 2
    left = merge_sort(a[:mid])                # ГИПОТЕЗА: вернёт отсортированный left
    right = merge_sort(a[mid:])               # ГИПОТЕЗА: вернёт отсортированный right
    return merge(left, right)                 # ЛЕММА: merge двух сортированных даёт сортированный


def merge(x: list[int], y: list[int]) -> list[int]:
    res, i, j = [], 0, 0
    # ИНВАРИАНТ: res отсортирован и содержит все элементы x[:i] и y[:j];
    #            любой элемент res <= любого из x[i:] и y[j:]
    while i < len(x) and j < len(y):
        if x[i] <= y[j]:                      # <= вместо < обеспечивает стабильность
            res.append(x[i]); i += 1
        else:
            res.append(y[j]); j += 1
    res.extend(x[i:]); res.extend(y[j:])
    return res

Обязательное условие корректности рекурсии: аргумент рекурсивного вызова строго меньше по некоторому вполне упорядоченному отношению. len(a[:mid]) < len(a) выполнено, потому что при len(a) ≥ 2 имеем 1 ≤ mid ≤ len(a) − 1. Забудьте про этот случай — и получите RecursionError на входе длины 1.

Кстати, в реальном мире это не паранойя: баг в Timsort из OpenJDK/Android/Python нашли именно формальной верификацией — инвариант на стеке ранов не выполнялся, и при особых входах случался ArrayIndexOutOfBoundsException. Работа de Gouw et al., CAV 2015: «OpenJDK’s java.utils.Collection.sort() is broken». Подробнее про Timsort — в статье о сортировках.

7. Нижние оценки: доказать, что быстрее нельзя

Верхняя оценка — это «я умею за O(f)». Нижняя — гораздо более сильное утверждение: «никто не сможет быстрее Ω(g) в такой-то модели».

Дерево решений для сортировок сравнением. Любой алгоритм, который узнаёт о данных только через сравнения aᵢ ? aⱼ, можно представить бинарным деревом: узлы — сравнения, листья — итоговые перестановки. Различных перестановок n!, каждая должна быть достижима, значит листьев ≥ n!. Бинарное дерево высоты h имеет не более 2^h листьев, следовательно 2^h ≥ n!, откуда по формуле Стирлинга:

h ≥ log₂(n!) = Θ(n log n)

Это тот самый барьер Ω(n log n), поэтому merge sort и heap sort оптимальны в модели сравнений. А radix sort и counting sort обходят его не «нарушая теорему», а работая в другой модели — они читают биты/цифры ключей, а не только сравнивают их.

Аргумент противника (adversary). Ещё одна техника: воображаемый оппонент отвечает на запросы алгоритма так, чтобы максимально долго сохранять неопределённость. Например, поиск максимума требует ≥ n − 1 сравнений: каждое сравнение «выбивает» максимум одного кандидата, а исключить нужно n − 1.

Про то, что бывает, когда нижних оценок нет и задача, похоже, экспоненциальна, — в NP-полноте и приближениях.

8. Память, случайность и «средний случай»

Память. Считается так же, как время, но не забывайте про две частые невидимки:

• стек рекурсии: Θ(log n) у quicksort с рекурсией по меньшей половине, но Θ(n) в худшем случае, если рекурсировать наивно;
• промежуточные копии: a[:mid] в примере выше — это Θ(n) аллокаций, поэтому «in-place merge sort» из учебника на самом деле требует Θ(n) дополнительной памяти.

Различают ещё входную память (её обычно не считают) и рабочую; алгоритм с O(log n) рабочей памяти называется работающим в логарифмическом пространстве.

Средний случай требует распределения. Фраза «в среднем O(n log n)» бессмысленна без указания, по какому распределению берётся среднее. Обычно предполагают равновероятность всех перестановок входа — сильное и часто неверное допущение (реальные данные почти отсортированы, или наоборот, приходят от злоумышленника).

Рандомизация переносит случайность внутрь алгоритма. Randomized quicksort даёт E[T(n)] = Θ(n log n) для любого входа — потому что случайность берётся из генератора, а не из данных. Это принципиально сильнее, и это тема рандомизированных алгоритмов.

Правый нижний угол — «галактические алгоритмы»: асимптотически прекрасные, но с константами, делающими их бесполезными на любых реальных данных. Умножение матриц за O(n^2.3719) (Alman–Williams, arxiv.org/abs/2010.05846) — чистая теория; на практике используют Штрассена и то лишь от n ≈ 1000.

9. Константы, которые нельзя игнорировать

Асимптотика — модель, а модель можно применить не по адресу. Где именно O врёт:

1. Малые n. Все промышленные сортировки переключаются на insertion sort для коротких участков: std::sort (introsort Массера) — на 16 элементах, CPython list.sort — на minrun из 32–64 элементов (см. подробный listsort.txt).
2. Кэш. Θ(n) обход связного списка может быть в 10–50 раз медленнее Θ(n) обхода массива: у списка каждый шаг — промах кэша. Отсюда популярность плоских структур (std::vector вместо std::list, B-деревья вместо бинарных).
3. Аллокации и GC. Θ(n log n) merge sort с созданием новых списков может проиграть Θ(n²) in-place сортировке на n = 5000 из-за давления на аллокатор.
4. Предсказание ветвлений. Ветвление с непредсказуемым исходом стоит ~15 циклов штрафа. Branchless-варианты бинарного поиска бывают быстрее «оптимального» кода.
5. Скрытые константы в структурах. Фибоначчиева куча даёт O(1) амортизированный decrease-key и теоретически ускоряет Дейкстру, но на практике проигрывает бинарной куче почти всегда (кратчайшие пути).

Правило: асимптотика решает, какой алгоритм; константы решают, какая реализация. Сначала уберите квадрат, потом деритесь за проценты.

10. Эмпирическая проверка: doubling test

Теорию нужно проверять. Самый простой и надёжный приём — тест удвоения (Sedgewick, algs4.cs.princeton.edu/14analysis): если T(n) ≈ c·n^b, то T(2n)/T(n) → 2^b. Значит, показатель степени восстанавливается как b = log₂(T(2n)/T(n)).

import math
import random
import time
from typing import Callable


def doubling_test(func: Callable[[list[int]], object],
                  n0: int = 1000, steps: int = 7, repeats: int = 3) -> None:
    """Оценивает эмпирический показатель степени b в T(n) ~ c * n^b.

    Отношение T(2n)/T(n) даёт 2^b: 2 → линейный, ~2.1-2.3 → n log n, 4 → квадрат.
    """
    prev = None
    n = n0
    print(f"{'n':>9} {'время, с':>12} {'T(2n)/T(n)':>12} {'оценка b':>10}")
    for _ in range(steps):
        data = [random.randint(0, 10**9) for _ in range(n)]
        best = min(_timed(func, data) for _ in range(repeats))  # min устойчивее среднего:
                                                                # шум всегда добавляет время
        if prev is None:
            print(f"{n:>9} {best:>12.5f} {'—':>12} {'—':>10}")
        else:
            ratio = best / prev
            b = math.log2(ratio) if ratio > 0 else float("nan")
            print(f"{n:>9} {best:>12.5f} {ratio:>12.2f} {b:>10.2f}")
        prev, n = best, n * 2


def _timed(func, data) -> float:
    payload = list(data)                 # копия: чтобы in-place алгоритм не получил
                                         # уже отсортированный вход на второй прогон
    start = time.perf_counter()
    func(payload)
    return time.perf_counter() - start


if __name__ == "__main__":
    doubling_test(sorted)                # ожидаем ratio ≈ 2.1-2.2, b ≈ 1.1

Что здесь принципиально и часто делается неправильно:

• min, а не среднее. Шум операционной системы, JIT, GC всегда добавляет время и никогда не убавляет; минимум ближе к «чистой» стоимости.
• Свежие данные на каждый прогон. Иначе in-place сортировка на втором прогоне получит отсортированный массив и покажет O(n).
• Прогрев. Для JIT-языков (Java, C#, JS) первые сотни итераций меряют компилятор, а не алгоритм. Используйте JMH, BenchmarkDotNet, criterion (Rust), go test -bench.
• Достаточно большие n. На n < 10⁴ вы меряете кэш и накладные расходы, а не рост.

Для системных замеров: perf stat (Linux), hyperfine для CLI-программ, py-spy/cProfile для Python. Подробнее — в практической оптимизации.

11. Как это выглядит в проде

Сложность как поверхность атаки. Если злоумышленник управляет входом, он может целенаправленно попасть в худший случай:

• Hash-flooding. Подобрав ключи с одинаковым хешем, атакующий превращает O(1) словарь в O(n) список и кладёт сервер. Классическая работа Crosby & Wallach, USENIX 2003 «Denial of Service via Algorithmic Complexity Attacks» (usenix.org). Ответ индустрии — SipHash со случайным секретом на процесс: сегодня он в Python (PYTHONHASHSEED), Rust, Ruby, Perl, ядре Linux.
• ReDoS. Регулярное выражение с вложенными квантификаторами даёт экспоненциальный backtracking. 2 июля 2019 года Cloudflare положил значительную часть своего трафика на 27 минут одним регулярным выражением с .*.*=.* в WAF — детальный и очень честный разбор: blog.cloudflare.com/details-of-the-cloudflare-outage-on-july-2-2019. Защита: движки на автоматах (RE2, Go regexp, Rust regex) с гарантией O(n).
• Квадратичный парсинг. Zip-бомбы, XML entity expansion, «billion laughs» — всё это атаки на сложность, а не на память как таковую.

Ревью-эвристики, которые ловят 90% инцидентов:

• запрос к БД внутри цикла — это N+1 и O(n) round-trip’ов;
• list.contains / array.includes внутри цикла — квадрат, заменяется set/map;
• конкатенация строк в цикле — квадрат, заменяется буфером/join;
• рекурсия по данным пользователя без ограничения глубины — переполнение стека;
• сортировка внутри цикла вместо одной сортировки снаружи;
• пагинация через OFFSET n — линейна по n, при глубокой пагинации используйте keyset-пагинацию (см. data engineering).

Асимптотика в capacity planning. Практический перевод: «мы вырастем в 10 раз за год». Для O(n) это ×10 к времени, для O(n log n) — примерно ×13, для O(n²) — ×100. Последнее означает, что система, отвечающая за 200 мс, будет отвечать 20 секунд. Именно это и есть тот момент, когда «академическая теория» превращается в постмортем.

Инварианты в проде — это не только доказательства. Формализованный инвариант естественно превращается в:

• assert / контракт (Debug.Assert, invariant() в Elixir-стиле через guard’ы);
• property-based тест: Hypothesis (Python), QuickCheck (Haskell), fast-check (TS), StreamData (Elixir);
• инвариант БД: constraint, unique index, check;
• метрика/алерт: «баланс счетов сходится», «очередь не растёт монотонно».

Property-based тестирование — самый дешёвый способ получить 80% пользы от доказательств: вы формулируете инвариант («после сортировки список упорядочен и является перестановкой исходного»), а фреймворк ищет контрпример:

from hypothesis import given, strategies as st

@given(st.lists(st.integers()))
def test_merge_sort_is_correct(xs):
    result = merge_sort(xs)
    assert all(result[i] <= result[i + 1] for i in range(len(result) - 1))  # упорядочен
    assert sorted(result) == sorted(xs)                                     # перестановка

Два assert — ровно два свойства из инварианта раздела 6. Это и есть практическое применение теории.

12. Чек-лист анализа

Перед тем как считать алгоритм готовым:

1. Модель. Что считаю элементарной операцией? Что такое n — длина массива, число рёбер, битовая длина числа?
2. Время. Худший случай в Θ. Средний — если указано распределение. Отдельно — амортизация, если есть редкие дорогие операции.
3. Память. Рабочая память, стек рекурсии, промежуточные копии.
4. Корректность. Предусловие, постусловие, инвариант каждого цикла, вариант (мера завершения) каждого цикла и рекурсии.
5. Границы. Пустой вход, один элемент, все элементы равны, максимальный размер, переполнение типов, отрицательные числа.
6. Устойчивость к злому входу. Что произойдёт, если данные подберёт атакующий?
7. Эмпирика. Doubling test подтверждает теоретическую степень?

Мини-итог

• Асимптотика описывает алгоритм, а не запуск; O, Ω, Θ — верхняя, нижняя и точная границы, а «худший/средний случай» — независимое от них измерение.
• Рекуррентности решаются деревом рекурсии, мастер-теоремой или подстановкой с индукцией; для неравных разбиений — Акра–Бацци.
• Амортизационный анализ (агрегат, бухгалтерия, потенциал) объясняет, почему редкие Θ(n)-операции не портят общую Θ(1) — но не даёт гарантий по p99-латентности.
• Корректность цикла = инициализация + сохранение + завершение; отдельно нужен вариант, доказывающий, что цикл вообще закончится.
• Нижние оценки (дерево решений, аргумент противника) говорят, когда улучшать уже нечего.
• Константы, кэш и аллокации решают исход, когда асимптотика одинакова; проверяйте теорию тестом удвоения и профилировщиком.

Источники

• Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms, 4-е изд. — главы 2–5 (инварианты, асимптотика, рекуррентности, амортизация): mitpress.mit.edu
• Sedgewick, Wayne. Algorithms, 4-е изд., раздел 1.4 «Analysis of Algorithms» — тильда-нотация и doubling hypothesis: algs4.cs.princeton.edu/14analysis
• Skiena. The Algorithm Design Manual, 3-е изд. — глава 2, прикладной взгляд на анализ: algorist.com
• Knuth. Big Omicron and Big Omega and Big Theta, SIGACT News, 1976: dl.acm.org/doi/10.1145/1008328.1008329
• Hoare. An Axiomatic Basis for Computer Programming, CACM, 1969: dl.acm.org/doi/10.1145/363235.363259
• Tarjan. Amortized Computational Complexity, SIAM J. Alg. Disc. Meth., 1985: epubs.siam.org/doi/10.1137/0606031
• Crosby, Wallach. Denial of Service via Algorithmic Complexity Attacks, USENIX 2003: usenix.org
• Cloudflare. Details of the Cloudflare outage on July 2, 2019: blog.cloudflare.com
• CPython listsort.txt — как теория превращается в промышленный код: github.com/python/cpython
• Hypothesis — property-based тестирование на Python: hypothesis.readthedocs.io

Что дальше

Мы научились измерять и доказывать. Пора применить это к самой изученной задаче в информатике — сортировке: там встретятся и нижняя оценка Ω(n log n), и инварианты, и амортизация, и та самая борьба констант, из-за которой промышленные сортировки — гибриды.

Сортировки: от пузырька до Timsort и radix