Амортизационный анализ

Амортизационный анализ — это метод анализа вычислительной сложности алгоритма, используемый в случаях, когда время исполнения одного шага алгоритма, умноженное на число шагов, даёт слишком большую оценку на время исполнения всего алгоритма по сравнению с тем, какая она на самом деле.

История

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

Метод

Основные статьи: Метод предоплаты и Метод потенциалов (амортизационный анализ)

Основной идеей амортизационного анализа является то, что любая трудоёмкая операция меняет состояние программы таким образом, что до следующей трудоёмкой операции обязательно пройдёт достаточно много мелких, тем самым «амортизируя» вклад трудоёмкой операции. Есть три основных метода ведения амортизированного анализа: агрегирующий анализ, метод предоплаты и метод потенциалов. Все три дают правильный ответ и в конкретном случае обычно выбирается наиболее удобный:

• При агрегирующем анализе вычисляется оценка сверху $T(n)$ на время исполнения $n$ операций, затем амортизационная сложность одной операции приравнивается к ${\textstyle T(n)/n}$.
• В методе предоплаты каждой операции заранее приписывается амортизированная стоимость, которая может отличаться от её реальной стоимости. При этом более «дешёвые» операции обычно имеют амортизированную стоимость выше реальной, а более «дорогие» имеют амортизированную стоимость ниже реальной. За счёт этого при исполнении дешёвых операций накапливается некоторая сумма, которую можно «потратить» на то, чтобы выполнить операцию, чья амортизированная стоимость ниже реальной. Считается, что изначальная сумма равна нулю и если в течение алгоритма она не становится отрицательной, то суммарное время работы алгоритма будет равно разности суммарной амортизированной стоимости операций и накопленной суммы. Таким образом, амортизированная стоимость операций является оценкой сверху для реальной стоимости при условии, что накопленная сумма не становится отрицательной.
• В методе потенциалов накопленная сумма вычисляется как функция («потенциал») от состояния структуры данных. Амортизированная стоимость при этом равна сумме реальной стоимости и изменения потенциала.

Примеры

Динамический массив

Амортизированный анализ операции push в динамическом массиве

В динамическом массиве помимо индексации есть операция push, которая добавляет элемент в конец массива и увеличивает его размер на единицу. Примерами такого массива являются контейнеры ArrayList в Java и std::vector в C++. Если изначально размер массива равен 4, в него можно добавить 4 элемента и каждое добавление будет занимать константное время. Добавление же пятого элемента потребует создания нового массива размера 8, в который будут перенесены элементы старого, а затем добавлен новый элемент. Следующие три операции push при этом снова будут занимать константное время, после чего массив снова придётся удвоить.

В общем случае, если было произведено $n+1$ операций push в массив размера $n$, все эти операции будут исполнены за константное время, кроме последней, которая займёт $\Theta (n)$. Из этого можно сделать вывод, что амортизированная стоимость добавления элемента в динамический массив равна ${\textstyle {\tfrac {n\Theta (1)+\Theta (n)}{n+1}}=\Theta (1)}$.

Примечания

• Allan Borodin and Ran El-Yaniv. Online Computation and Competitive Analysis (англ.). — Cambridge University Press, 1998. — P. 20,141.