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

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

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

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

Для последовательности операций , можно определить:

Суммарное амортизированное время: Суммарное реальное время:

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

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

Из того, что и следует неравенство , как и было сказано ранее.

Примеры

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

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

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

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

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

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

Применения Метод потенциалов обычно используется для анализа фибоначчиевых куч, в которых извлечение элемента требует амортизированно логарифмического времени, а все остальные операции занимают амортизированно константное времяCormen et al., Chapter 20, «Fibonacci Heaps», pp. 476—497.. Также с его помощью можно показать, что splay-дерево обладает логарифмической амортизированной стоимостью операцийGoodrich and Tamassia, Section 3.4, «Splay Trees», pp. 185—194..

Примечания

Категория:Анализ алгоритмов