Метод потенциалов. Этот метод является обобщением метода предоплаты. Здесь резерв определяется функцией состояния структуры данных в целом. Эта функция называется потенциалом.
Общая схема метода такова. Пусть над структурой данных предстоит произвести операций, и пусть — состояние структуры данных после -й операции ( — исходное состояние). Потенциал представляет собой функцию
из множества возможных состояний структуры данных в множество действительных чисел.
Пусть — реальная стоимость -й операции. Учетной стоимостью -й операции объявим число , определяемое формулой
как сумма реальной стоимости операции плюс приращение потенциала в результате выполнения этой операции. Тогда суммарная учетная стоимость всех операций равна
Если нам удалось придумать функцию , для которой
то суммарная учетная стоимость даст верхнюю оценку для реальной стоимости последовательности из операций. Не ограничивая общности, можно считать, что
Говоря неформально, если разность потенциалов
положительна, то учетная стоимость -й операции включает в себя резерв (предоплату за будущие операции); если же эта разность отрицательна, то учетная стоимость -й операции меньше реальной и разница покрывается за счет накопленного к этому моменту потенциала.
Учетные стоимости и оценки реальной стоимости, рассчитанные с помощью метода потенциалов, зависят от выбора потенциальной функции, а сам этот выбор является делом творческим.
Ниже эти три метода будут проиллюстрированы на примере анализа работы двоичного счетчика с единственной операцией Increment (прибавление единицы).