Зачем три разных метода

В предыдущем уроке мы использовали «банковский метод» (он же accounting). Это один из трёх классических способов доказать амортизированную сложность. В литературе по алгоритмам (Cormen, Tarjan) используются:

1. Aggregate method — посчитать суммарную стоимость T(n) для n операций и поделить на n.
2. Accounting method (банковский) — выдавать каждой операции «амортизированную плату», часть которой откладывается на будущие дорогие операции.
3. Potential method — определить «потенциал» структуры (как энергия), и считать amortized = actual + delta(potential).

Все три дают один и тот же ответ для динамического массива (amortized O(1)), но смотрят на проблему с разных сторон. Знание разных формулировок помогает применять амортизацию к другим структурам — splay tree, fibonacci heap, union-find.

Aggregate method — суммарный взгляд

Самый прямой способ. Возьмём растущий с x2 dynamic array. После n операций append, сколько работы сделано суммарно?

Каждый append стоит 1 «единицу» (запись в slot). Плюс, в момент resize, стоит N единиц (копирование). Resize происходит, когда длина достигает степени двойки: 1, 2, 4, 8, …, n. Суммарная стоимость copy:

1 + 2 + 4 + 8 + ... + n/2 + n ≈ 2n

Это геометрическая прогрессия, сумма меньше 2n. Плюс n единиц на сам append. Итого ~3n. Делим на n операций: amortized cost = 3 = O(1).

Просто. Прямолинейно. Главное — заметить геометрический ряд и не запутаться в индексах.

Accounting method — банковский

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

Для x2 vector:

• Объявляем амортизированную плату append = 3.
• Реальная плата дешёвого append = 1. Излишек +2 кладём в банк (на этот slot, и на slot-«дублёра» в копии).
• Реальная плата resize n -> 2n = n (копирование). Откуда взять? К моменту resize n новых элементов лежат в массиве, и каждый положил в банк по 2 единицы. Итого в банке 2n единиц — хватает с запасом.

Доказательство: банк никогда не уходит в минус. Значит amortized плата (3) — корректная верхняя граница.

Это удобно, когда у разных операций разные стоимости, и вы хотите тонко настроить «налоги». Например, для splay tree разные ротации стоят по-разному.

Potential method — энергетический

Самый формальный. Вводим функцию потенциала Φ от состояния структуры. Amortized cost операции = actual cost + ΔΦ.

Для x2 vector: пусть Φ = 2 * (len - capacity/2). Это «энергия» того, как много элементов мы добавили после прошлого resize. После resize Φ = 0 (свежий буфер). Перед resize Φ = 2 * (n - n/2) = n.

• Дешёвый append: actual = 1, ΔΦ = 2 (потенциал растёт на 2). Amortized = 3.
• Resize append: actual = n + 1 (n copy + 1 write), но ΔΦ = 2 * (n/2) - n ≈ -n + что-то. Amortized = n + 1 - n = O(1).

Сумма amortized по всем операциям = сумма actual + (Φ_final - Φ_initial). Если Φ ≥ 0 всегда и Φ_initial = 0, то сумма actual ≤ сумма amortized. То есть amortized — верхняя граница реальной суммарной стоимости.

Этот метод выигрывает на сложных структурах (splay tree, фибоначчи-куча), где надо одновременно ограничивать стоимости разных операций.

Аналогия для трёх методов

Amortized vs Average vs Expected

Этот пункт обязательно нужно понимать, потому что junior часто путает:

• Average-case — среднее по входным данным при случайных входах в рамках одного запуска. Связан с теорией вероятности. Например, average для quicksort O(n log n) при равномерно случайных входах.

• Expected (ожидаемое) — то же по сути, для рандомизированных алгоритмов. Например, expected O(n log n) для randomized quicksort при ЛЮБЫХ входах, но с рандомизированным выбором pivot.

• Amortized — среднее по последовательности операций над структурой. Никакой случайности. Гарантия в худшем случае на серию операций. Конкретный append может стоить O(n), но сумма N append всегда ≤ c * N.

Иными словами, amortized — это детерминистическая гарантия, а не статистическая. Это важно для систем с SLA: при amortized O(1) суммарное время всегда укладывается, хотя отдельные операции могут спайкить.

Когда amortized не достаточно

Для real-time, для p99/p999 SLA — нужен worst-case, не amortized. Поэтому в hard real-time системах не любят dynamic array: они дают spike. Используют либо pre-allocated буферы, либо incremental data structures (например, lazy resize — копировать по 1-2 элемента на каждом append, размазывая работу).

Для DE-нагрузок — пакетных, throughput-oriented — amortized совершенно достаточно. 99% времени вы заливаете данные в буфер, и общее время идёт ровно. Spike в 1 ms на одном append из миллиона никто не заметит.

Попробуй сам

Зафиксируйте spike-операции, чтобы увидеть amortized vs worst-case:

import time

def measure_each(n):
    """Возвращает массив времён каждого append в наносекундах."""
    xs = []
    times = []
    for i in range(n):
        t0 = time.perf_counter_ns()
        xs.append(i)
        t1 = time.perf_counter_ns()
        times.append(t1 - t0)
    return times

times = measure_each(100_000)

# найдём p50, p99, p99.9, max
sorted_t = sorted(times)
n = len(sorted_t)
print(f"p50:   {sorted_t[n // 2]} ns")
print(f"p99:   {sorted_t[n * 99 // 100]} ns")
print(f"p99.9: {sorted_t[n * 999 // 1000]} ns")
print(f"max:   {sorted_t[-1]} ns")
print(f"avg:   {sum(times) // n} ns")

Скорее всего, увидите что-то такое:

p50:    65 ns
p99:    110 ns
p99.9:  450 ns
max:    8500 ns       # вот они, resize spikes
avg:    72 ns

p99 близко к p50 (амортизация работает), но max на два порядка больше — это и есть момент resize. Average и p99 хорошие, worst — плохой.