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