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

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

Определения

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

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

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

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

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

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

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

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

${\displaystyle 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}),}$

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

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

Примеры

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

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

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

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

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

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

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

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

Применения

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

Примечания

1. Goodrich, Michael T.; Tamassia, Roberto (2002), "1.5.1 Amortization Techniques", Algorithm Design: Foundations, Analysis and Internet Examples, Wiley, pp. 36–38.
2. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. 18.3 метод потенциалов // Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — С. 412—416. — ISBN 5-8459-0857-4.
3. Cormen et al., Chapter 20, «Fibonacci Heaps», pp. 476—497.
4. Goodrich and Tamassia, Section 3.4, «Splay Trees», pp. 185—194.