Метод потенциалов (амортизационный анализ)

Метод потенциалов — один из методов амортизационного анализа, позволяющий «сгладить» влияние дорогих, но редких операций на суммарную вычислительную сложность алгоритма.

Определения

В методе потенциалов вводится функция $\Phi$, связывающая состояние структуры данных с некоторым неотрицательным числом. Смысл данной функции заключается в том, что если $S$ — текущее состояние структуры, то $\Phi (S)$ — это величина, характеризующая объём работы «дорогих» операций, который уже был «оплачен» более дешёвыми операциями, но не был произведён. Таким образом, $\Phi (S)$ может рассматриваться как аналог потенциальной энергии, ассоциированной с данным состоянием. Изначально значение потенциальное функции обычно полагается равным нулю.

Пусть $o$ — некоторая отдельная операция из серии, $S_{before}$ — состояние структуры до этой операции, а $S_{after}$ — после неё. Тогда амортизированная сложность операции $o$ равна

$T_{\mathrm {amortized} }(o)=T_{\mathrm {actual} }(o)+\Phi (S_{\mathrm {after} })-\Phi (S_{\mathrm {before} }).$

Соотношения между амортизированной и реальной стоимостью

Суммарная амортизированная стоимость последовательности операций является валидной оценкой сверху для реальной стоимости этой последовательности операций.

Для последовательности операций $O=o_{1},o_{2},\dots ,o_{n}$, можно определить:

• Суммарное амортизированное время: $T_{\mathrm {amortized} }(O)=\sum _{i=0}^{n}T_{\mathrm {amortized} }(o_{i}),$
• Суммарное реальное время: $T_{\mathrm {actual} }(O)=\sum _{i=0}^{n}T_{\mathrm {actual} }(o_{i}).$

В таких обозначениях:

$T_{\mathrm {amortized} }(O)=\sum _{i=1}^{n}\left(T_{\mathrm {actual} }(o_{i})+\Phi (S_{i})-\Phi (S_{i-1})\right)=T_{\mathrm {actual} }(O)+\Phi (S_{n})-\Phi (S_{0}),$

Таким образом, последовательность значений потенциальной функции образует телескопическую сумму, в которой последовательные начальные и конечные значения потенциальной функции сокращаются друг с другом.

Из того, что $\Phi (S_{0})=0$ и $\Phi (S_{n})\geq 0$ следует неравенство $T_{\mathrm {actual} }(O)\leq T_{\mathrm {amortized} }(O)$, как и было сказано ранее.

Примеры

Стек с массовыми удалениями

Можно рассмотреть вариант стека, поддерживающий следующие операции:

• initialize — создать пустой стек.
• push — добавить единственный элемент на верхушку стека, увеличив его размер на $1$.
• pop(k) — убрать $k$ элементов с верхушки стека, где $k$ не превосходит текущий размер стека.

Одна операция pop(k) требует $O(k)$ времени, совокупное же время работы может быть проанализировано с помощью следующей потенциальной функции $\Phi (S)$, равной числу элементов в стеке $S$. Данная величина всегда неотрицательна, при этом операция push работает за константу и увеличивает $\Phi$ на единицу, а операция pop работает за $O(k)$, но также уменьшает потенциальную функцию на $k$, поэтому её амортизированное время также константно. Из этого следует, что суммарное время исполнения любой последовательности из $m$ операций равно $O(m)$ в худшем случае.

Двоичный счётчик

Другим примером является счётчик, реализованный в виде двоичного числа, поддерживающего такие операции:

• initialize -- создать счётчик со значением $0$.
• inc — увеличить значение счётчика на $1$.

Чтобы показать, что амортизированная стоимость inc равна $O(1)$, следует рассмотреть потенциальную функцию, равную числу бит счётчика, равных $1$ (вес Хемминга счётчика). Как и требуется, такая функция всегда неотрицательна и изначально равна $0$. Операция inc сперва инвертирует младший значимый бит счётчика, а затем, если он был равен $1$, повторяет то же самое со следующим битом, пока не наткнётся на $0$. Если до этого в конце битовой записи счётчика было $k$ единичных битов, потребуется инвертировать $k+1$ бит, затрачивая $k+1$ единиц реального времени и уменьшая потенциал на $k-1$. Таким образом, амортизированная стоимость операции inc равна $2$ и, как следствие, время исполнения $m$ операций inc равно $O(m)$.

Применения

Метод потенциалов обычно используется для анализа фибоначчиевых куч, в которых извлечение элемента требует амортизированно логарифмического времени, а все остальные операции занимают амортизированно константное время. Также с его помощью можно показать, что splay-дерево обладает логарифмической амортизированной стоимостью операций.