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

Амортизированный анализ (amortized analysis) — метод оценки среднего времени операции в серии из n операций, когда отдельные операции могут быть дорогими, но редко, а суммарная стоимость остаётся низкой.

Зачем нужно

Big O описывает наихудшую стоимость одной операции. Но иногда дорогая операция встречается настолько редко, что среднее по серии гораздо ниже. Если не применять амортизированный анализ, можно ошибочно посчитать алгоритм неэффективным. Именно поэтому Array.push называют O(1) амортизированно, хотя изредка требует O(n) на расширение буфера.

Где используется

  • Динамические массивы (ArrayList, Vector, JS Array): расширение буфера
  • Хеш-таблицы: рехеширование при превышении load factor
  • Стек с операцией multipop
  • Splay-деревья: самобалансирующиеся деревья
  • Union-Find с path compression

Основной контент

Три метода амортизированного анализа

1. Метод агрегирования (aggregate method)

Суммируем суммарную стоимость n операций, делим на n.

Пример: динамический массив

Добавление n элементов:
- Расширение происходит при заполнении: 1, 2, 4, 8, ..., n
- Суммарная стоимость копирований: 1 + 2 + 4 + ... + n = O(2n) = O(n)
- На n операций: O(n) / n = O(1) амортизированно

2. Метод банкира (accounting/banker method)

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

// Динамический массив: каждый push "платит" 3 единицы
// 1 — на саму вставку
// 1 — на будущее копирование этого элемента
// 1 — на будущее копирование старого элемента
// При удвоении все кредиты уже накоплены → баланс ≥ 0

3. Метод потенциала (potential method)

Определяем функцию потенциала Φ, отражающую «накопленный долг» структуры.

Φ(массив) = 2 * (число элементов) - (ёмкость)

Амортизированная стоимость = реальная стоимость + ΔΦ

При обычном push (нет расширения):
  реальная = 1, ΔΦ = +2 → амортиз. = 3

При расширении (k→2k, добавляем 1 элемент):
  реальная = k+1, ΔΦ = 2*(k+1) - 2k - (k) = 2-k
  амортиз. = (k+1) + (2-k) = 3 → O(1)

Сравнение с worst-case

// Наивная оценка push: O(n) в худшем случае
// Амортизированная: O(1) на операцию в среднем по n операциям

// Важно: амортизированное ≠ среднее по входам (average case)
// Амортизированное — гарантия для ЛЮБОЙ последовательности операций

Примеры структур и их амортизированных сложностей

Структура / Операция Worst-case Амортизированная
Array.push O(n) O(1)
Hash table insert O(n) O(1)
Stack multipop(k) O(k) O(1) на операцию
Splay tree find O(n) O(log n)
Union-Find с path compression O(log n) O(α(n)) ≈ O(1)

Частые ошибки

  • Путать амортизированную сложность со средней (average case): амортизированная гарантирована для любой последовательности, средняя — статистическая.
  • Называть push «всегда O(1)» — корректнее «O(1) амортизированно».
  • Применять амортизированный анализ к системам реального времени без учёта пиковых задержек: одна дорогая операция может нарушить latency-требования.

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

Ресурсы