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

TL;DR

Амортизационный анализ (amortized analysis) доказывает, что средняя стоимость операции за длинную последовательность мала, даже если отдельный вызов дорог. Это детерминированная гарантия: она не предполагает ни вероятностного распределения входов (как средний случай), ни случайных битов алгоритма (как ожидаемый случай). Есть три метода: агрегатный (поделить суммарную стоимость всех [math]\displaystyle{ m }[/math] операций на [math]\displaystyle{ m }[/math]), предоплата/accounting (одни операции «платят» кредиты, другие их тратят) и потенциал/physicist's (задать функцию состояния [math]\displaystyle{ \Phi }[/math] и считать [math]\displaystyle{ \hat c = c + \Delta\Phi }[/math]). Классические выводы: push_back в динамический массив — [math]\displaystyle{ O(1) }[/math] амортизированно; [math]\displaystyle{ n }[/math] инкрементов двоичного счётчика — [math]\displaystyle{ \le 2n }[/math] переворотов; СНМ — [math]\displaystyle{ O(\alpha(n)) }[/math]; splay-дерево — [math]\displaystyle{ O(\log n) }[/math] амортизированно. Важнейшая оговорка: амортизированные оценки не переносятся на персистентные структуры, где одну операцию можно повторить из разных версий (см. Персистентная очередь).

Свойство	Значение
Класс	Метод анализа алгоритмов и структур данных
Изобретение	метод потенциала и термин — Р. Тарьян, 1985 (систематизация)
Что даёт	границу суммарной стоимости последовательности операций
Гарантия	детерминированная (не вероятностная)
Методы	агрегатный, предоплата (accounting), потенциал (physicist's)
Ключевая формула	[math]\displaystyle{ \hat c_i = c_i + \Phi(S_i) - \Phi(S_{i-1}) }[/math]
Основное тождество	[math]\displaystyle{ \sum \hat c_i = \sum c_i + \Phi(S_m) - \Phi(S_0) }[/math]
Типичные примеры	динамический массив, двоичный счётчик, multipop-стек, СНМ, splay, фибоначчиевы кучи
Не то же самое, что	средний случай, ожидаемый случай, худший случай
Альтернативы	худший случай, средний случай, ожидаемый случай, рандомизация
Ограничение	не переносится на персистентные структуры без спецприёмов
Где встречается	стандартные библиотеки, СНМ, splay-деревья, фибоначчиевы кучи, персистентные структуры

Определения

Последовательность операций — серия из [math]\displaystyle{ m }[/math] вызовов над структурой, начинающаяся из фиксированного начального состояния.

Амортизированная стоимость (amortized cost) — величина, приписываемая операции так, что сумма амортизированных стоимостей ограничивает сумму реальных стоимостей: [math]\displaystyle{ \sum_{i=1}^{m} \hat c_i \ge \sum_{i=1}^{m} c_i }[/math]. Именно это и означает «амортизированно [math]\displaystyle{ O(1) }[/math]»: суммарная работа за [math]\displaystyle{ m }[/math] операций есть [math]\displaystyle{ O(m) }[/math].

Агрегатный метод. Оценить суммарную стоимость [math]\displaystyle{ T(m) }[/math] всех [math]\displaystyle{ m }[/math] операций и объявить амортизированную стоимость равной [math]\displaystyle{ T(m)/m }[/math]. См. рис. 1.

Метод предоплаты (accounting method). Каждой операции приписывается платёж [math]\displaystyle{ \hat c_i }[/math]; разность [math]\displaystyle{ \hat c_i - c_i }[/math] — кредит, накапливаемый на элементах структуры. Инвариант: суммарный кредит никогда не отрицателен, поэтому суммарный платёж покрывает реальные затраты.

Метод потенциала (physicist's / potential method). Задаётся потенциальная функция [math]\displaystyle{ \Phi(S) \ge 0 }[/math] на состояниях структуры. Амортизированная стоимость операции [math]\displaystyle{ i }[/math], переводящей состояние [math]\displaystyle{ S_{i-1} }[/math] в [math]\displaystyle{ S_i }[/math], равна

[math]\displaystyle{ \hat c_i = c_i + \Phi(S_i) - \Phi(S_{i-1}) = c_i + \Delta\Phi_i . }[/math]

Суммируя, получаем телескопирование: [math]\displaystyle{ \sum_{i=1}^{m} \hat c_i = \sum_{i=1}^{m} c_i + \Phi(S_m) - \Phi(S_0) }[/math].

В примере с динамическим массивом ниже принято соглашение cap = 0 в пустом массиве (как в Асимптотическая сложность): тогда [math]\displaystyle{ \Phi(S_0) = 0 }[/math] и [math]\displaystyle{ \Phi \ge 0 }[/math] выполняется всегда.

Амортизированный случай — не то же, что средний. Средний случай усредняет по распределению входов; ожидаемый — по случайным битам алгоритма; амортизированный — по последовательности операций при фиксированном (любом) входе.

Обозначения. [math]\displaystyle{ m }[/math] — число операций; [math]\displaystyle{ c_i }[/math] — реальная стоимость [math]\displaystyle{ i }[/math]-й операции; [math]\displaystyle{ \hat c_i }[/math] — амортизированная; [math]\displaystyle{ S_i }[/math] — состояние после [math]\displaystyle{ i }[/math] операций; [math]\displaystyle{ \Phi }[/math] — потенциал; [math]\displaystyle{ \log }[/math] — двоичный.

Рис. 1. Три метода: агрегатный, предоплата и потенциал — разные способы доказать одну суммарную оценку.

Мотивация и интуиция

Худший случай — пессимистичная оценка: если push_back иногда стоит [math]\displaystyle{ \Theta(n) }[/math], «худший [math]\displaystyle{ O(n) }[/math]» верен, но бесполезен для практики, ведь дорогие вставки редки. Считать средний случай по распределению входов тоже не всегда уместно: входы не случайны, а модель распределения может быть неизвестна. Амортизационный анализ даёт гарантию для любого входа, но не на каждый вызов, а на серию операций.

Идея — размазать редкие дорогие операции по дешёвым. Двоичный счётчик: младший бит переворачивается каждый шаг, следующий — через раз, третий — через три, и так далее. Суммарно за [math]\displaystyle{ n }[/math] инкрементов набегает не больше [math]\displaystyle{ 2n }[/math] переворотов, то есть [math]\displaystyle{ O(1) }[/math] на шаг в среднем (см. рис. 2). Динамический массив: копирование при удвоении стоит [math]\displaystyle{ \Theta(k) }[/math], но происходит всё реже, и в пересчёте на вставку — [math]\displaystyle{ O(1) }[/math]. Подробности — в Асимптотическая сложность.

Рис. 2. Дорогие шаги с переворотом многих битов редки; за [math]\displaystyle{ n }[/math] инкрементов набегает не больше [math]\displaystyle{ 2n }[/math] переворотов.

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

Устройство

Три метода отличаются способом ведения «бухгалтерии» (см. рис. 1).

Потенциал как «счёт» структуры

Метод потенциала — самый гибкий и чаще всего применяемый (см. рис. 3). Функция [math]\displaystyle{ \Phi(S) }[/math] измеряет «накопленный излишек» состояния: она растёт, когда структура «богата» (много дешёвых операций оплатили будущее), и падает при дорогой операции. Амортизированная стоимость [math]\displaystyle{ \hat c = c + \Delta\Phi }[/math] сглаживает пики.

Рис. 3. Реальные затраты скачут, амортизированная стоимость постоянна: потенциал копит разницу и отдаёт её на дорогой операции.

Требования к [math]\displaystyle{ \Phi }[/math]:

• [math]\displaystyle{ \Phi }[/math] определена для всех состояний структуры (обычно [math]\displaystyle{ \Phi \ge 0 }[/math]);
• операция может изменить [math]\displaystyle{ \Phi }[/math] на любую величину, но [math]\displaystyle{ \Phi(S_i) - \Phi(S_{i-1}) }[/math] должна быть вычислима и ограничена;
• из [math]\displaystyle{ \hat c_i = O(1) }[/math] для всех [math]\displaystyle{ i }[/math] следует [math]\displaystyle{ \sum c_i = \sum \hat c_i - \Phi(S_m) + \Phi(S_0) = O(m) }[/math] при [math]\displaystyle{ \Phi(S_m) \ge \Phi(S_0) }[/math].

Для динамического массива принимается соглашение cap = 0 в пустом массиве: тогда [math]\displaystyle{ \Phi = 0 }[/math] в начальном состоянии, и [math]\displaystyle{ \Phi \ge 0 }[/math] выполняется на всех состояниях.

Важно: если [math]\displaystyle{ \Phi }[/math] может упасть ниже [math]\displaystyle{ \Phi(S_0) }[/math], то из [math]\displaystyle{ \hat c_i = O(1) }[/math] уже не следует [math]\displaystyle{ \sum c_i = O(m) }[/math]: телескопирование даёт [math]\displaystyle{ \sum c_i = \sum \hat c_i + \Phi(S_0) - \Phi(S_m) }[/math], а последняя разность может быть велика. Тогда берут [math]\displaystyle{ \Phi }[/math] со сдвигом или доказывают [math]\displaystyle{ \Phi(S_m) \ge \Phi(S_0) }[/math] отдельно.

Агрегатный и accounting в сравнении

• Агрегатный метод не приписывает стоимость отдельным операциям — только всей серии. Это проще, но грубее: он не различает дорогие и дешёвые вызовы.
• Предоплата — неформальный аналог потенциала: кредит, отложенный на элементе, играет роль локального потенциала. Формально метод предоплаты можно смоделировать потенциалом, равным сумме кредитов.

Операции и алгоритмы

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

Операция: Increment — агрегатный метод

Идея. Стоимость Increment равна числу перевёрнутых битов. Оценим сумму переворотов за [math]\displaystyle{ n }[/math] инкрементов.

Пошаговое описание:

1. Найти младший нулевой бит, обнуляя встреченные единицы.
2. Установить этот бит в 1.
3. Стоимость шага — число изменённых битов.

Инвариант. Бит [math]\displaystyle{ i }[/math] переворачивается ровно один раз за каждые [math]\displaystyle{ 2^i }[/math] инкрементов.

Алгоритм Increment(C)
Вход:  счётчик C[0..k−1] (C[0] — младший бит); n — длина серии (параметр анализа)
Выход: C увеличен на 1; flips — число перевёрнутых битов на этом вызове
Инвариант: бит i переворачивается ровно один раз за каждые 2^i инкрементов
Сложность: O(1) амортизированно; O(k) в худшем вызове; O(n) за n шагов
Корректность: бит i меняется ⌊n/2^i⌋ раз, сумма < 2n

1  i ← 0
2  flips ← 0
3  while i < k and C[i] = 1
4      C[i] ← 0
5      flips ← flips + 1
6      i ← i + 1
7  if i < k
8      C[i] ← 1
9      flips ← flips + 1
10 return flips

Агрегатный анализ: бит i переворачивается ⌊n/2ⁱ⌋ раз за n инкрементов.
Σᵢ ⌊n/2ⁱ⌋ < n·(1 + 1/2 + 1/4 + …) = 2n.
Значит, суммарно ≤ 2n → амортизированно O(1) на инкремент.

Разбор. Последовательность 0000 → 0001 → 0010 → 0011 → 0100: число переворотов [math]\displaystyle{ 1, 2, 1, 3, \dots }[/math]; суммы за [math]\displaystyle{ n }[/math] шагов дают [math]\displaystyle{ \le 2n }[/math].

Сложность. Амортизированно [math]\displaystyle{ O(1) }[/math]; худший отдельный вызов — [math]\displaystyle{ O(\log n) }[/math]. Суммарно за [math]\displaystyle{ n }[/math] шагов — [math]\displaystyle{ O(n) }[/math].

Крайние случаи. Переполнение счётчика (все биты 1): при фиксированной длине [math]\displaystyle{ k }[/math] дальнейший инкремент не определён; при раскрытии — редкое [math]\displaystyle{ O(k) }[/math] событие, не портящее амортизации.

Операция: Push и Multipop — метод предоплаты

Идея. push кладёт элемент и предоплачивает его будущее извлечение. multipop(k) снимает до [math]\displaystyle{ k }[/math] элементов, тратя кредиты, накопленные их push.

Пошаговое описание:

1. push(x): положить элемент, назначить платёж ĉ = 2: 1 покрывает сам push, 1 остаётся кредитом.
2. multipop(k): снимать элементы, списывая по 1 кредиту за каждый, пока есть элементы и [math]\displaystyle{ k \gt 0 }[/math].
3. Инвариант: суммарный кредит неотрицателен.

Инвариант. Кредит структуры равен числу элементов в стеке; каждый элемент несёт «оплаченное» извлечение.

Операция Push(S, x)
Вход:  стек S; элемент x
Выход: x на вершине S; кредит увеличен на 1
1  push(S, x)
2  credits(S) ← credits(S) + 1

Операция Multipop(S, k)
Вход:  стек S; k ≥ 0 — максимум извлекаемых элементов
Выход: из S снято min(k, |S|) элементов, кредит уменьшен на столько же
1  while k > 0 and not Empty(S)
2      pop(S)
3      credits(S) ← credits(S) − 1
4      k ← k − 1

Инвариант: кредит структуры равен числу элементов в стеке: credits(S) = |S| ≥ 0.
Сложность: Push — O(1) реально и амортизированно (ĉ = 2);
           Multipop — O(k) реально, O(1) амортизированно (ĉ = 0, платит кредитами).
Корректность: каждый pop оплачен кредитом своего push, кредит неотрицателен,
              поэтому платёж 2 за каждый push покрывает все реальные затраты.
Анализ: платёж Push — 2, Multipop — 0 (тратит кредиты) → амортизированно O(1).

Разбор. 1000 push накапливают 1000 кредитов; multipop(400) тратит 400 и не уходит в минус; повторный multipop опустошает стек.

Сложность. push — [math]\displaystyle{ O(1) }[/math]; multipop(k) — [math]\displaystyle{ O(k) }[/math] реально, но [math]\displaystyle{ O(1) }[/math] амортизированно; суммарно за [math]\displaystyle{ m }[/math] операций — [math]\displaystyle{ O(m) }[/math].

Крайние случаи. multipop на пустом стеке — 0 операций; k больше размера — снимается весь стек.

Операция: Push-Back — метод потенциала

Идея. Взять [math]\displaystyle{ \Phi = 2\cdot\text{size} - \text{cap} }[/math]; в пустом массиве cap = 0, поэтому [math]\displaystyle{ \Phi = 0 }[/math] и [math]\displaystyle{ \Phi \ge 0 }[/math] всегда. На дешёвой вставке потенциал растёт («копим»), на крупном копировании падает, оплачивая работу. Тогда [math]\displaystyle{ \hat c \le 3 }[/math] всегда (см. рис. 4).

Пошаговое описание:

1. Если size = cap — удвоить ёмкость и скопировать элементы (стоимость cap = size).
2. Увеличить size, записать элемент.
3. Считать [math]\displaystyle{ \Delta\Phi }[/math] и [math]\displaystyle{ \hat c = c + \Delta\Phi }[/math].

Инвариант. [math]\displaystyle{ \Phi(S_i) \ge \Phi(S_0) = 0 }[/math]; амортизированная стоимость каждой вставки не превосходит 3.

Операция Push-Back(A, x)
Вход:  динамический массив A; A[1..size] — занятая часть (1-based); поля size и cap
Выход: x добавлен в конец A
Потенциал: Φ = 2·size − cap; в пустом массиве cap = 0, Φ = 0
1  if size = cap
2      копировать элементы в новый буфер    # копируется size = cap элементов; при cap = 0 — ноль
3      cap ← max(1, 2·cap)
4  size ← size + 1
5  A[size] ← x

Анализ:
  первая (cap = 0): c = 1, ΔΦ = +1, ĉ = 2;
  обычная вставка:  c = 1, ΔΦ = +2, ĉ = 3;
  при удвоении:     c = size+1, ΔΦ = 2 − cap = 2 − size, ĉ = 3.
  Итог: ĉ ≤ 3 на любую вставку → O(1) амортизированно, Σ c = O(n).
Инвариант: Φ = 2·size − cap ≥ 0; ĉ ≤ 3.
Сложность: реально O(1) или O(size); амортизированно O(1).
Корректность: Σ c = Σ ĉ − Φ(S_m) + Φ(S_0) ≤ 3m, так как Φ(S_m) ≥ 0 = Φ(S_0).

Разбор. 16 вставок копируют [math]\displaystyle{ 1+2+4+8 = 15 }[/math] элементов — меньше [math]\displaystyle{ n }[/math]; каждая вставка, кроме первой, имеет [math]\displaystyle{ \hat c = 3 }[/math], первая — [math]\displaystyle{ \hat c = 2 }[/math], что и доказывает [math]\displaystyle{ O(1) }[/math].

Сложность. Реально push_back — [math]\displaystyle{ O(1) }[/math] или [math]\displaystyle{ O(\text{size}) }[/math]; амортизированно [math]\displaystyle{ O(1) }[/math].

Крайние случаи. Рост на константу (cap+1) даёт [math]\displaystyle{ \Theta(size) }[/math] копий на каждую вставку и [math]\displaystyle{ \Theta(n^2) }[/math] суммарно — удвоение критично.

Рис. 4. Копии при удвоении происходят на вставках 2, 3, 5 и 9; [math]\displaystyle{ \Phi = 2\cdot\text{size} - \text{cap} }[/math] копится на дешёвых вставках и падает на 5-й и 9-й, поэтому [math]\displaystyle{ \hat c \le 3 }[/math].

Сводная таблица сложности

Пример	Реальная стоимость операции	Амортизированная	Метод	Потенциал / кредит
Двоичный счётчик	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(1) }[/math]	агрегатный	—
Стек с multipop	[math]\displaystyle{ O(k) }[/math]	[math]\displaystyle{ O(1) }[/math]	предоплата	1 кредит на элемент
Динамический массив	[math]\displaystyle{ O(1)/O(n) }[/math]	[math]\displaystyle{ O(1) }[/math]	потенциал	[math]\displaystyle{ 2\cdot\text{size} - \text{cap} }[/math]
СНМ (ранг + сжатие)	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\alpha(n)) }[/math]	потенциал	по деревьям
splay-дерево	[math]\displaystyle{ O(n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	потенциал	логарифмы размеров
Фибоначчиева куча	insert — [math]\displaystyle{ O(1) }[/math]; decrease-key — до [math]\displaystyle{ O(\log n) }[/math]	insert и decrease-key — [math]\displaystyle{ O(1) }[/math]	потенциал	число деревьев

Оговорка: амортизированная оценка — гарантия на серию операций при любом входе; отдельный вызов может быть дороже. Для оценки на каждый вызов нужен худший случай.

Память всех перечисленных структур — [math]\displaystyle{ O(n) }[/math] на хранение самих элементов; амортизация меняет оценку времени, но не памяти (кредиты и потенциал — это учётные величины, а не дополнительные копии данных).

Трассировка примера

Проследим push_back с удвоением (реализация из раздела «Служебное»). Принято cap = 0 в пустом массиве, поэтому [math]\displaystyle{ \Phi(S_0) = 0 }[/math]. [math]\displaystyle{ \Phi }[/math] считается до и после операции.

Вставка	cap	size	[math]\displaystyle{ c }[/math] (реально)	[math]\displaystyle{ \Phi }[/math] после	[math]\displaystyle{ \Delta\Phi }[/math]	[math]\displaystyle{ \hat c = c + \Delta\Phi }[/math]
старт	0	0	—	0	—	—
1	1	1	1	1	+1	2
2	2	2	2	2	+1	3
3	4	3	3	2	0	3
4	4	4	1	4	+2	3
5	8	5	5	2	−2	3
6	8	6	1	4	+2	3

Каждая строка, кроме первой, даёт [math]\displaystyle{ \hat c = 3 }[/math]; первая — 2, потому что копировать ещё нечего. Сумма [math]\displaystyle{ \sum\hat c = 3m - 1 \le 3m }[/math], а [math]\displaystyle{ \sum c = \sum\hat c - \Phi(S_m) + \Phi(S_0) \le 3m }[/math] (так как [math]\displaystyle{ \Phi(S_m) \ge \Phi(S_0) }[/math]), то есть [math]\displaystyle{ O(m) }[/math]. Для [math]\displaystyle{ m = 6 }[/math]: [math]\displaystyle{ \sum\hat c = 17 }[/math], [math]\displaystyle{ \sum c = 13 }[/math], тождество [math]\displaystyle{ 17 = 13 + 4 - 0 }[/math] сходится.

Для двоичного счётчика: за [math]\displaystyle{ n }[/math] шагов число переворотов равно [math]\displaystyle{ 2n - \mathrm{popcount}(n) }[/math] — например, для [math]\displaystyle{ n = 8 }[/math] это [math]\displaystyle{ 16 - 1 = 15 }[/math]; проверяется прогоном (см. «Служебное»).

Корректность и оценка сложности

Корректность метода потенциала

Утверждение. Если [math]\displaystyle{ \hat c_i = c_i + \Phi(S_i) - \Phi(S_{i-1}) }[/math] и [math]\displaystyle{ \Phi(S_m) \ge \Phi(S_0) }[/math], то [math]\displaystyle{ \sum_{i=1}^{m} c_i \le \sum_{i=1}^{m} \hat c_i }[/math].

Доказательство. Телескопическая сумма: [math]\displaystyle{ \sum_{i=1}^{m} \hat c_i = \sum c_i + \sum (\Phi(S_i) - \Phi(S_{i-1})) = \sum c_i + \Phi(S_m) - \Phi(S_0) }[/math]. Отсюда [math]\displaystyle{ \sum c_i = \sum \hat c_i - (\Phi(S_m) - \Phi(S_0)) \le \sum \hat c_i }[/math], если [math]\displaystyle{ \Phi(S_m) \ge \Phi(S_0) }[/math]. Значит, из [math]\displaystyle{ \hat c_i = O(1) }[/math] для всех [math]\displaystyle{ i }[/math] следует [math]\displaystyle{ \sum c_i = O(m) }[/math]. [math]\displaystyle{ \square }[/math]

Корректность агрегатного метода

Если доказано [math]\displaystyle{ T(m) \le g(m) }[/math] для всех последовательностей из [math]\displaystyle{ m }[/math] операций, то амортизированная стоимость [math]\displaystyle{ g(m)/m }[/math] ограничивает среднюю, а суммарная стоимость — [math]\displaystyle{ g(m) }[/math]. Здесь неявно предполагается, что операции можно выполнять в любом порядке — оценка для наихудшей серии.

Корректность предоплаты

Если платёж [math]\displaystyle{ \hat c_i }[/math] назначается так, что кредит структуры неотрицателен после каждой операции, то сумма платежей покрывает суммарную реальную стоимость. Формально кредит можно отождествить с потенциалом: [math]\displaystyle{ \Phi(S) = }[/math] сумма кредитов в состоянии [math]\displaystyle{ S }[/math], и метод предоплаты становится частным случаем метода потенциала.

Границы: персистентность (см. рис. 5)

Амортизированные оценки не композируются с персистентностью. Причина: одна и та же операция может быть выполнена из разных версий, поэтому «работа на серию» не сохраняется. Пример — очередь на двух стеках: pop амортизированно [math]\displaystyle{ O(1) }[/math] в одной линии операций, но при ветвлении версий разворот повторяется, и отдельный вызов снова стоит [math]\displaystyle{ \Theta(n) }[/math].

Рис. 5. При ветвлении версий дорогая операция повторяется в каждой ветви — амортизированная оценка на серию перестаёт действовать.

Поэтому для персистентных структур применяют банкирскую очередь (кредиты в структуре), физическую (потенциал) или очередь реального времени (планировщик, [math]\displaystyle{ O(1) }[/math] в худшем случае) — см. Персистентная очередь и Очередь на шести стеках.

Сравнение с альтернативами

Четыре оценки отвечают на разные вопросы (см. рис. 6).

Оценка	Что берём	Гарантия	Пример
Худший случай	максимум по входам	каждый вызов [math]\displaystyle{ \le }[/math] оценка	quicksort [math]\displaystyle{ O(n^2) }[/math]
Средний случай	по распределению входов	нужна модель входов	quicksort [math]\displaystyle{ O(n\log n) }[/math]
Ожидаемый случай	по случайности алгоритма	любой вход, случайные биты	ранд. quicksort
Амортизированный	по последовательности операций	любая серия, любой вход	push_back, СНМ, splay

Рис. 6. Четыре оценки отвечают на разные вопросы: худший случай — максимум по входам, амортизированный — гарантия на серию.

Вердикт. Худший случай — когда нужна гарантия реального времени. Средний/ожидаемый — когда допустима вероятностная модель. Амортизированный — когда структура используется как серия операций и редкие дорогие вызовы приемлемы. В персистентном контексте — только кредит/потенциал внутри структуры или худший случай.

Где применяется

Все примеры ниже устроены одинаково: редкая дорогая операция оплачивается массой дешёвых (см. рис. 7).

1. Стандартные библиотеки. std::vector::push_back (и его аналоги в других языках) — [math]\displaystyle{ O(1) }[/math] амортизированно; std::unordered_map при перехешировании — [math]\displaystyle{ O(1) }[/math] амортизированно. Почему: расти динамически без [math]\displaystyle{ O(n) }[/math] на каждую вставку можно только с удвоением и амортизацией [1][4].

1. Структуры данных для графов. Фибоначчиевы кучи — Фибоначчиева куча — дают insert и decrease-key за [math]\displaystyle{ O(1) }[/math] амортизированно, ускоряя Дейкстру и Прима. Почему: консолидация ленивая, а её стоимость амортизируется [1][3].

1. Система непересекающихся множеств. Union/Find с объединением по рангу и сжатием путей — [math]\displaystyle{ O(\alpha(n)) }[/math] амортизированно, где [math]\displaystyle{ \alpha }[/math] — обратная функция Аккермана. Почему: анализ проводится методом потенциала [1][3].

1. Самоподстраивающиеся деревья. Splay-дерево — Splay-дерево — [math]\displaystyle{ O(\log n) }[/math] амортизированно при отдельных вызовах до [math]\displaystyle{ O(n) }[/math]; адаптируется к частым доступам. Почему: потенциал, основанный на весах поддеревьев [2].

1. Компиляторы и системы. Динамические буферы, пулы памяти, ленивые структуры и перехеширование таблиц — везде, где «дорогое расширение» редкое и должно быть размазано [4][5].

Рис. 7. Общий шаблон применений: редкие дорогие операции оплачиваются массой дешёвых.

Историческая справка

Понятие амортизированного анализа и его три метода систематизировали Роберт Тарьян (R. E. Tarjan) в работе Amortized Computational Complexity (SIAM Journal on Algebraic and Discrete Methods, 1985); он же широко применял метод потенциала [3]. Анализ системы непересекающихся множеств с обратной функцией Аккермана [math]\displaystyle{ \alpha(n) }[/math] восходит к Тарьяну (1975), уточнён им совместно с ван Левеном (1984) [1][3].

Splay-деревья и их амортизированный анализ представили Дэниел Слитор и Роберт Тарьян (Self-Adjusting Binary Search Trees, Journal of the ACM, 1985) [2]. Фибоначчиевы кучи ввели Майкл Фредман и Роберт Тарьян (Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms, Journal of the ACM, 1987) [1]. Двоичный счётчик и multipop-стек — классические учебные примеры, разобранные, например, в CLRS (гл. 17) [1].

Термин «амортизированный» (от английского amortize — «распределять, погашать») закрепился в алгоритмической литературе после работ Тарьяна ⚠️ требует проверки точной атрибуции термина.

Типичные ошибки и подводные камни

• Путать амортизированный случай со средним. Амортизация — детерминированная гарантия на серию, а не усреднение по входам и не вероятностный анализ.
• Считать оценку гарантией на каждый вызов. «[math]\displaystyle{ O(1) }[/math] амортизированно» допускает отдельные [math]\displaystyle{ O(n) }[/math] вызовы; для реального времени это неприемлемо.
• Некорректный потенциал. Если [math]\displaystyle{ \Phi }[/math] может упасть ниже [math]\displaystyle{ \Phi(S_0) }[/math], оценка [math]\displaystyle{ \sum c_i \le \sum\hat c_i }[/math] теряется. Проверяйте [math]\displaystyle{ \Phi \ge 0 }[/math] (или [math]\displaystyle{ \Phi(S_m) \ge \Phi(S_0) }[/math]).
• Неверный знак в [math]\displaystyle{ \hat c }[/math]. Формула [math]\displaystyle{ \hat c = c + \Delta\Phi }[/math]; путаница знака легко превращает доказательство в бессмыслицу.
• Забыть про рост на константу. Динамический массив с cap+1 теряет амортизацию ([math]\displaystyle{ \Theta(n^2) }[/math]); нужен геометрический рост (удвоение).
• Переносить амортизацию на персистентность. При ветвлении версий дорогая операция «переигрывается»; нужны кредит/потенциал внутри структуры или планировщик.
• Складывать амортизированные оценки разных операций без учёта их влияния на Φ. Потенциал общий; увеличение работы одной операции может сократить запас для другой.
• Забывать про «амортизированное» при разговоре о параллельности. В многопоточном коде амортизация может нарушаться из-за конкуренции; там важнее худший случай.
• Ошибочно считать multipop независимой операцией. Его дешевизна оплачена предыдущими push; без единого учёта кредита вывод неверен.
• Использовать агрегатный метод там, где нужна стоимость операции. Он даёт лишь суммарную оценку и не различает вызовы.

Задачи для практики

1. Двоичный счётчик. Для [math]\displaystyle{ n }[/math] инкрементов из нуля найдите точное число переворотов и докажите, что оно равно [math]\displaystyle{ 2n - \mathrm{popcount}(n) }[/math]. Подсказка: вклад бита [math]\displaystyle{ i }[/math] — [math]\displaystyle{ \lfloor n/2^i\rfloor }[/math]. Ответ. [math]\displaystyle{ 2n - \mathrm{popcount}(n) }[/math]; вклад бита [math]\displaystyle{ i }[/math] равен [math]\displaystyle{ \lfloor n/2^i\rfloor }[/math], сумма по [math]\displaystyle{ i }[/math] даёт [math]\displaystyle{ 2n - \mathrm{popcount}(n) }[/math]; сложность [math]\displaystyle{ O(n) }[/math].

1. Динамический массив. Докажите [math]\displaystyle{ \hat c \le 3 }[/math] для [math]\displaystyle{ \Phi = 2\cdot\text{size} - \text{cap} }[/math]. Подсказка: разберите случаи «без копирования» и «с копированием». Ответ. Без копирования [math]\displaystyle{ c = 1 }[/math], [math]\displaystyle{ \Delta\Phi = +2 }[/math], [math]\displaystyle{ \hat c = 3 }[/math]; при удвоении [math]\displaystyle{ c = \text{size}+1 }[/math], [math]\displaystyle{ \Phi }[/math] падает до 2, [math]\displaystyle{ \Delta\Phi = 2 - \text{size} }[/math], [math]\displaystyle{ \hat c = 3 }[/math].

1. Рост на константу. Покажите, что при cap ← cap + 1 суммарная стоимость [math]\displaystyle{ n }[/math] вставок есть [math]\displaystyle{ \Theta(n^2) }[/math]. Подсказка: сумма арифметической прогрессии. Ответ. [math]\displaystyle{ \sum_{i=1}^{n} i = n(n+1)/2 = \Theta(n^2) }[/math].

1. multipop. Докажите, что суммарная стоимость [math]\displaystyle{ m }[/math] операций push/multipop есть [math]\displaystyle{ O(m) }[/math]. Подсказка: каждый элемент снимается не более одного раза. Ответ. Каждый элемент снимается не более раза, поэтому суммарное число снятий [math]\displaystyle{ \le m }[/math], а с учётом push — [math]\displaystyle{ \le 2m }[/math].

1. Потенциал для multipop. Подберите [math]\displaystyle{ \Phi }[/math], равный размеру стека, и выведите [math]\displaystyle{ \hat c = O(1) }[/math]. Подсказка: push увеличивает [math]\displaystyle{ \Phi }[/math] на 1, pop уменьшает на 1. Ответ. [math]\displaystyle{ \Phi = |S| }[/math]; push: [math]\displaystyle{ \hat c = 1 + 1 = 2 }[/math]; pop: [math]\displaystyle{ \hat c = 1 - 1 = 0 }[/math].

1. СНМ. Объясните, почему объединение по рангу без сжатия путей даёт [math]\displaystyle{ O(\log n) }[/math], а со сжатием — [math]\displaystyle{ O(\alpha(n)) }[/math]. Подсказка: сжатие уменьшает высоты будущих деревьев. Ответ. Без сжатия высота [math]\displaystyle{ \le \log n }[/math], find — [math]\displaystyle{ O(\log n) }[/math]; сжатие даёт [math]\displaystyle{ O(\alpha(n)) }[/math] амортизированно (Тарьян, 1975).

1. Splay. Приведите пример последовательности, где splay-дерево выполняет операцию за [math]\displaystyle{ O(n) }[/math], но серия из [math]\displaystyle{ m }[/math] операций — за [math]\displaystyle{ O(m\log n) }[/math]. Подсказка: потенциал на размерах поддеревьев. Ответ. Доступ к самому глубокому узлу — [math]\displaystyle{ O(n) }[/math]; серия из [math]\displaystyle{ m }[/math] доступов — [math]\displaystyle{ O(m\log n) }[/math] по потенциалу на размерах поддеревьев.

1. Персистентность. Постройте пример, где амортизированная оценка ломается при ветвлении, и покажите, как потенциал «внутри структуры» это исправляет. Подсказка: см. Персистентная очередь. Ответ. После разворота возникают две версии; каждая ветвь снова платит [math]\displaystyle{ \Theta(n) }[/math]; банкирская очередь держит кредиты внутри структуры, поэтому оценка сохраняется.

Связанные темы

• Асимптотическая сложность — обозначения [math]\displaystyle{ O }[/math], [math]\displaystyle{ \Theta }[/math] и место амортизации.
• Система непересекающихся множеств — [math]\displaystyle{ O(\alpha(n)) }[/math] амортизированно.
• Splay-дерево — амортизированный анализ через потенциал.
• Фибоначчиева куча — [math]\displaystyle{ O(1) }[/math] амортизированно для insert/decrease-key.
• Персистентная очередь — где амортизация перестаёт работать.
• Очередь на шести стеках — [math]\displaystyle{ O(1) }[/math] в худшем случае как альтернатива амортизации.
• Двоичная куча — build-heap за [math]\displaystyle{ O(n) }[/math] (агрегатный анализ).

Источники

1. Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms (CLRS). 3rd ed. — MIT Press, 2009. — Гл. 17 «Amortized Analysis» (aggregate, accounting, potential); фибоначчиевы кучи (гл. 19).
2. Sleator D. D., Tarjan R. E. Self-Adjusting Binary Search Trees // Journal of the ACM. — 1985. — Vol. 32, № 3 (splay-деревья и потенциал).
3. Tarjan R. E. Amortized Computational Complexity // SIAM J. Algebraic and Discrete Methods. — 1985. — Vol. 6, № 2; Tarjan R. E. Efficiency of a Good But Not Linear Set Union Algorithm // JACM. — 1975.
4. Sedgewick R., Wayne K. Algorithms. 4th ed. — Addison-Wesley, 2011. — §1.4 (анализ, амортизация для динамических массивов).
5. Okasaki C. Purely Functional Data Structures. — Cambridge University Press, 1998 (кредит и потенциал в функциональных структурах).
6. Fredman M. L., Tarjan R. E. Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms // Journal of the ACM. — 1987. — Vol. 34, № 3.
7. Wikipedia: Amortized analysis. URL: https://en.wikipedia.org/wiki/Amortized_analysis.