Амортизационный анализ: Групповой, Банковский и Метод потенциалов

В чем суть амортизационного анализа?

В некоторых структурах данных отдельная операция может стоить очень дорого (например, $O(N)$ при расширении массива std::vector), но происходит это настолько редко, что среднее время на операцию в последовательности из $M$ операций составляет $O(1)$.

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

---

3 фундаментальных метода амортизационного анализа

1. Групповой метод (Aggregate Analysis)

Показываем, что суммарная стоимость последовательности из $n$ операций ограничена $T(n)$. Тогда амортизированная стоимость одной операции:

Пример (Динамический массив): Копирование при переполнении происходит на шагах $1, 2, 4, 8, 16, \dots$.

2. Банковский метод (Accounting / Credit Method)

Каждой операции назначается учетная стоимость $\hat{c}_i$.

Если $\hat{c}_i > c_i$ (реальная стоимость), излишек $\hat{c}_i - c_i$ кладется на «банковский счет» элемента в виде кредита;

Если $\hat{c}_i < c_i$, недостающая стоимость оплачивается накопленным ранее кредитом;

Баланс счета всегда должен оставаться $\ge 0$: $\sum_{i=1}^n \hat{c}_i \ge \sum_{i=1}^n c_i$.

3. Метод потенциалов (Potential Method)

Определяется потенциальная функция $\Phi(D)$, отображающая состояние структуры $D$ в действительное число $\mathbb{R}$ (с условием $\Phi(D_i) \ge \Phi(D_0)$).

Амортизированная стоимость $i$-й операции определяется как:

Сумма амортизированных стоимостей: