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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

История[править | править код]

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

Метод[править | править код]

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

  • При агрегирующем анализе вычисляется оценка сверху на время исполнения операций, затем амортизационная сложность одной операции приравнивается к [4].
  • В методе предоплаты[en] каждой операции заранее приписывается амортизированная стоимость, которая может отличаться от её реальной стоимости. При этом более «дешёвые» операции обычно имеют амортизированную стоимость выше реальной, а более «дорогие» имеют амортизированную стоимость ниже реальной. За счёт этого при исполнении дешёвых операций накапливается некоторая сумма, которую можно «потратить» на то, чтобы выполнить операцию, чья амортизированная стоимость ниже реальной. Считается, что изначальная сумма равна нулю и если в течение алгоритма она не становится отрицательной, то суммарное время работы алгоритма будет равно разности суммарной амортизированной стоимости операций и накопленной суммы. Таким образом, амортизированная стоимость операций является оценкой сверху для реальной стоимости при условии, что накопленная сумма не становится отрицательной[4].
  • В методе потенциалов накопленная сумма вычисляется как функция («потенциал») от состояния структуры данных. Амортизированная стоимость при этом равна сумме реальной стоимости и изменения потенциала[4].

Примеры[править | править код]

Динамический массив[править | править код]

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

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

В общем случае, если было произведено операций push в массив размера , все эти операции будут исполнены за константное время, кроме последней, которая займёт . Из этого можно сделать вывод, что амортизированная стоимость добавления элемента в динамический массив равна [4].

Примечания[править | править код]

  1. Lecture 7: Amortized Analysis. Carnegie Mellon University. Дата обращения 14 марта 2015.
  2. Tarjan, Robert Endre. Amortized Computational Complexity (англ.) // SIAM Journal on Algebraic and Discrete Methods (англ.) : journal. — 1985. — April (vol. 6, no. 2). — P. 306—318. — doi:10.1137/0606031.
  3. Rebecca Fiebrink (2007), Amortized Analysis Explained, <http://www.cs.princeton.edu/~fiebrink/423/AmortizedAnalysisExplained_Fiebrink.pdf>. Проверено 3 мая 2011.  Архивная копия от 20 октября 2013 на Wayback Machine
  4. 1 2 3 4 5 Kozen, Dexter CS 3110 Lecture 20: Amortized Analysis. Cornell University (Spring 2011). Дата обращения 14 марта 2015.