Метод предоплаты и метод потенциалов

Коротко

Кроме агрегатного, есть два тонких метода. Предоплата (учётный): назначаешь операции цену-предоплату, отличную от настоящей; переплата копится как КРЕДИТ на структуре и потом платит за дорогие операции. Кредит не должен уходить в минус. Потенциал: заводишь функцию Φ от состояния структуры («запас энергии»), и амортизированная цена ĉ = c + Φ_после − Φ_до. Дешёвая операция копит Φ, дорогая тратит. Оба дают ту же оценку, что агрегатный, но гибче.

Если умеешь доказывать амортизированную оценку и методом предоплаты (кредит ≥ 0), и методом потенциалов (ĉ = c + ΔΦ), листай до «Теперь сам».

Как думаешь, зачем ещё два метода

Агрегатный метод даёт одну среднюю цену на все операции сразу. Но операций бывает несколько видов (в стек кладут и достают), и хочется у каждого своя амортизированная цена. Для этого и нужны два других метода: они назначают цену покаждой операции, а не делят общую сумму поровну. Заодно они не требуют считать всю серию наперёд - доказательство идёт локально, шаг за шагом.

На что это похоже

Предоплата - как абонемент: платишь чуть больше за дешёвые походы в зал, копишь на счёте, и дорогой поход (с тренером) уже оплачен заранее. Главное - счёт не уходит в минус, иначе «оплачено заранее» неправда. Потенциал - как заряд батареи: дешёвые операции её заряжают, дорогая разряжает, и пока заряд не падает ниже стартового, все дорогие всплески уже покрыты накопленным.

Механизм: предоплата и потенциал

Предоплата. Каждой операции назначаешь амортизированную цену ĉ - можно не равную настоящей c. Если ĉ > c, разница кладётся КРЕДИТОМ на структуру; если ĉ < c, недостаток берётся из накопленного кредита. Требование одно: суммарный кредит НИКОГДА не уходит в минус. Тогда Σĉ ≥ Σc, и Σĉ - честная верхняя оценка всей серии.

Потенциал. Заводишь функцию Φ(D) ≥ 0 от состояния структуры D (обычно Φ пустой структуры = 0). Амортизированная цена операции:

ĉ = c + Φ(D_после) − Φ(D_до)

Просуммируем по всей серии - соседние Φ сокращаются (телескоп):

Σĉ = Σc + Φ(D_n) − Φ(D_0)

Раз Φ(D_0) = 0 и Φ(D_n) ≥ 0, получаем Σĉ ≥ Σc - снова верхняя оценка. Дешёвая операция поднимает Φ (копит про запас), дорогая роняет Φ (тратит запас), и её большая c гасится отрицательным ΔΦ.

Правило

Предоплата: назначь ĉ, следи, чтобы кредит Σĉ − Σc ≥ 0 всегда. Потенциал: задай Φ ≥ 0 с Φ(D_0) = 0, тогда ĉ = c + ΔΦ. Кредит и потенциал - одно и то же число с двух сторон: накопленный кредит и есть значение Φ.

Разбор: стек методом предоплаты

Стек с операциями push, pop и multipop(k) (снять k элементов). Настоящие цены: push и pop по 1, multipop(k) - k. Назначим предоплату: push = 2, pop = 0, multipop = 0. При push платим 1 за само добавление, а 1 кладём кредитом НА этот элемент. Когда элемент снимают (pop или multipop), его снятие уже оплачено лежащим на нём кредитом - поэтому назначенная цена снятия 0. Кредит не уходит в минус: на каждом лежащем в стеке элементе ровно 1. Значит любая серия из n операций стоит не больше 2n - амортизированно O(1) на операцию, хотя один multipop бывает Θ(n).

Разбор: тот же стек методом потенциалов

Возьмём Φ(D) = число элементов в стеке. Она ≥ 0, а на пустом стеке = 0 - условия выполнены. Считаем ĉ = c + ΔΦ:

push: c = 1, элементов стало на один больше, ΔΦ = +1. ĉ = 1 + 1 = 2.
pop: c = 1, ΔΦ = −1. ĉ = 1 − 1 = 0.
multipop(k): c = k (сняли k), ΔΦ = −k. ĉ = k − k = 0.

Каждая операция амортизированно O(1), включая multipop. Заметь: Φ = число элементов - это ровно суммарный кредит из метода предоплаты (1 на элемент). Два метода - один и тот же запас, записанный по-разному.

Разбор: считаем серию по шагам

Проследим серию push, push, push, multipop(3) с потенциалом Φ = высота стека, считая ĉ = c + ΔΦ:

push:         c=1, Φ 0→1, ĉ = 1+1 = 2
push:         c=1, Φ 1→2, ĉ = 1+1 = 2
push:         c=1, Φ 2→3, ĉ = 1+1 = 2
multipop(3):  c=3, Φ 3→0, ĉ = 3−3 = 0
настоящих действий: 1+1+1+3 = 6
амортизированных:   2+2+2+0 = 6

Суммы сошлись: Σĉ = Σc = 6, потому что Φ вернулась к нулю (Φ(конец) = Φ(старт) = 0). Три дешёвых push подняли потенциал до 3, и дорогой multipop(3) полностью его израсходовал - оттого и вышел бесплатным. Если бы серия кончилась при непустом стеке, Σĉ было бы даже больше Σc на остаток Φ - оценка с запасом, но всё ещё верная.

Что ломается без этого

Две ловушки. В предоплате - забыть проверить, что кредит не уходит в минус: если дорогая операция случится раньше, чем накоплен кредит, «предоплата» ничего не доказывает. В потенциале - взять Φ, которая бывает отрицательной или не ноль на старте: тогда Φ(D_n) − Φ(D_0) может оказаться отрицательным, Σĉ < Σc, и оценка перестаёт быть верхней. Φ ≥ 0 и Φ(D_0) = 0 - не формальность, а то, что делает Σĉ гарантией.

Зачем это в работе

Метод потенциалов - главный инструмент для структур со сложным поведением: динамические массивы, splay-деревья, фибоначчиевы кучи доказывают свои оценки именно им, потому что агрегатно их серию не сложить. Умение подобрать Φ - это и есть «увидеть, где структура копит запас на будущее»: у стека запас - его высота, у динамического массива (следующий урок) - насколько он заполнен сверх половины.

Теперь сам

Стек считают методом потенциалов с Φ = число элементов. Чему равна амортизиро‐ ванная цена push, за которым сразу идёт multipop, снимающий всё (пусть в стеке стало m элементов перед ним)?

Ответ. push: ĉ = 1 + 1 = 2. Следующий multipop(m): снимает все m, c = m, ΔΦ = −m (стек опустел), ĉ = m − m = 0. Вместе две операции стоят амортизированно 2 + 0 = 2 = O(1), хотя настоящая цена второй Θ(m). Накопленный за push-и потенциал (высота стека) ровно оплатил дорогой multipop - Φ упала с m до 0, погасив его цену.

Главное

Два тонких метода. Предоплата: назначь операции цену ĉ, переплата копится кредитом, недостаток берётся из него, кредит всегда ≥ 0 - тогда Σĉ ≥ Σc. Потенциал: задай Φ ≥ 0 c Φ(D_0)=0, и ĉ = c + Φ_после − Φ_до; при суммировании средние Φ телескопируются, остаётся Σĉ = Σc + Φ(D_n) ≥ Σc. Дешёвая операция копит запас, дорогая его тратит. У стека Φ = высота, и это тот же кредит 1 на элемент - multipop амортизированно O(1).