Русская Википедия:Метод потенциалов (амортизационный анализ)
Шаблон:Значения Метод потенциалов — один из методов амортизационного анализа, позволяющий «сгладить» влияние дорогих, но редких операций на суммарную вычислительную сложность алгоритма[1][2].
Определения
В методе потенциалов вводится функция <math>\Phi</math>, связывающая состояние структуры данных с некоторым неотрицательным числом. Смысл данной функции заключается в том, что если <math>S</math> — текущее состояние структуры, то <math>\Phi(S)</math> — это величина, характеризующая объём работы «дорогих» операций, который уже был «оплачен» более дешёвыми операциями, но не был произведён. Таким образом, <math>\Phi(S)</math> может рассматриваться как аналог потенциальной энергии, ассоциированной с данным состоянием[1][2]. Изначально значение потенциальное функции обычно полагается равным нулю.
Пусть <math>o</math> — некоторая отдельная операция из серии, <math>S_{before}</math> — состояние структуры до этой операции, а <math>S_{after}</math> — после неё. Тогда амортизированная сложность операции <math>o</math> равна
- <math>T_\mathrm{amortized}(o) = T_\mathrm{actual}(o) + \Phi(S_\mathrm{after}) - \Phi(S_\mathrm{before}).</math>
Соотношения между амортизированной и реальной стоимостью
Суммарная амортизированная стоимость последовательности операций является валидной оценкой сверху для реальной стоимости этой последовательности операций.
Для последовательности операций <math>O = o_1, o_2, \dots,o_n </math>, можно определить:
- Суммарное амортизированное время: <math>T_\mathrm{amortized}(O) = \sum_{i=0}^n T_\mathrm{amortized}(o_i),</math>
- Суммарное реальное время: <math>T_\mathrm{actual}(O) = \sum_{i=0}^n T_\mathrm{actual}(o_i).</math>
В таких обозначениях:
- <math>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),</math>
Таким образом, последовательность значений потенциальной функции образует телескопическую сумму, в которой последовательные начальные и конечные значения потенциальной функции сокращаются друг с другом.
Из того, что <math>\Phi(S_0) = 0</math> и <math>\Phi(S_n)\ge 0</math> следует неравенство <math>T_\mathrm{actual}(O) \leq T_\mathrm{amortized}(O)</math>, как и было сказано ранее.
Примеры
Стек с массовыми удалениями
Можно рассмотреть вариант стека, поддерживающий следующие операции:
- initialize — создать пустой стек.
- push — добавить единственный элемент на верхушку стека, увеличив его размер на <math>1</math>.
- pop(k) — убрать <math>k</math> элементов с верхушки стека, где <math>k</math> не превосходит текущий размер стека.
Одна операция pop(k) требует <math>O(k)</math> времени, совокупное же время работы может быть проанализировано с помощью следующей потенциальной функции <math>\Phi(S)</math>, равной числу элементов в стеке <math>S</math>. Данная величина всегда неотрицательна, при этом операция push работает за константу и увеличивает <math>\Phi</math> на единицу, а операция pop работает за <math>O(k)</math>, но также уменьшает потенциальную функцию на <math>k</math>, поэтому её амортизированное время также константно. Из этого следует, что суммарное время исполнения любой последовательности из <math>m</math> операций равно <math>O(m)</math> в худшем случае.
Двоичный счётчик
Другим примером является счётчик, реализованный в виде двоичного числа, поддерживающего такие операции:
- initialize -- создать счётчик со значением <math>0</math>.
- inc — увеличить значение счётчика на <math>1</math>.
Чтобы показать, что амортизированная стоимость inc равна <math>O(1)</math>, следует рассмотреть потенциальную функцию, равную числу бит счётчика, равных <math>1</math> (Шаблон:Не переведено 5 счётчика). Как и требуется, такая функция всегда неотрицательна и изначально равна <math>0</math>. Операция inc сперва инвертирует младший значимый бит счётчика, а затем, если он был равен <math>1</math>, повторяет то же самое со следующим битом, пока не наткнётся на <math>0</math>. Если до этого в конце битовой записи счётчика было <math>k</math> единичных битов, потребуется инвертировать <math>k+1</math> бит, затрачивая <math>k+1</math> единиц реального времени и уменьшая потенциал на <math>k-1</math>. Таким образом, амортизированная стоимость операции inc равна <math>2</math> и, как следствие, время исполнения <math>m</math> операций inc равно <math>O(m)</math>.
Применения
Метод потенциалов обычно используется для анализа фибоначчиевых куч, в которых извлечение элемента требует амортизированно логарифмического времени, а все остальные операции занимают амортизированно константное время[3]. Также с его помощью можно показать, что splay-дерево обладает логарифмической амортизированной стоимостью операций[4].
Примечания
- ↑ 1,0 1,1 Шаблон:Citation.
- ↑ 2,0 2,1 Книга:CLRS
- ↑ Cormen et al., Chapter 20, «Fibonacci Heaps», pp. 476—497.
- ↑ Goodrich and Tamassia, Section 3.4, «Splay Trees», pp. 185—194.
