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

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

Определения

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

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

$T_{\mathrm{a}\mathrm{m}\mathrm{o}\mathrm{r}\mathrm{t}\mathrm{i}\mathrm{z}\mathrm{e}\mathrm{d}}(o)=T_{\mathrm{a}\mathrm{c}\mathrm{t}\mathrm{u}\mathrm{a}\mathrm{l}}(o)+\mathrm{\Phi }(S_{\mathrm{a}\mathrm{f}\mathrm{t}\mathrm{e}\mathrm{r}})-\mathrm{\Phi }(S_{\mathrm{b}\mathrm{e}\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{e}}).$

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

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

Для последовательности операций $O=o_1,o_2,\dots ,o_n$, можно определить:

• Суммарное амортизированное время: $T_{\mathrm{a}\mathrm{m}\mathrm{o}\mathrm{r}\mathrm{t}\mathrm{i}\mathrm{z}\mathrm{e}\mathrm{d}}(O)=\sum _{i=0}^n{T}_{\mathrm{a}\mathrm{m}\mathrm{o}\mathrm{r}\mathrm{t}\mathrm{i}\mathrm{z}\mathrm{e}\mathrm{d}}(o_i),$
• Суммарное реальное время: $T_{\mathrm{a}\mathrm{c}\mathrm{t}\mathrm{u}\mathrm{a}\mathrm{l}}(O)=\sum _{i=0}^n{T}_{\mathrm{a}\mathrm{c}\mathrm{t}\mathrm{u}\mathrm{a}\mathrm{l}}(o_i).$

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

$T_{\mathrm{a}\mathrm{m}\mathrm{o}\mathrm{r}\mathrm{t}\mathrm{i}\mathrm{z}\mathrm{e}\mathrm{d}}(O)=\sum _{i=1}^n(T_{\mathrm{a}\mathrm{c}\mathrm{t}\mathrm{u}\mathrm{a}\mathrm{l}}(o_i)+\mathrm{\Phi }(S_i)-\mathrm{\Phi }(S_{i-1}))=T_{\mathrm{a}\mathrm{c}\mathrm{t}\mathrm{u}\mathrm{a}\mathrm{l}}(O)+\mathrm{\Phi }(S_n)-\mathrm{\Phi }(S_0),$

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

Из того, что $\mathrm{\Phi }(S_0)=0$ и $\mathrm{\Phi }(S_n)\ge 0$ следует неравенство $T_{\mathrm{a}\mathrm{c}\mathrm{t}\mathrm{u}\mathrm{a}\mathrm{l}}(O)\le T_{\mathrm{a}\mathrm{m}\mathrm{o}\mathrm{r}\mathrm{t}\mathrm{i}\mathrm{z}\mathrm{e}\mathrm{d}}(O)$, как и было сказано ранее.

Примеры

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

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

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

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

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

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

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

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

Применения

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