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

Основные определения

Определение:

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

Такой анализ чаще всего используется, чтобы показать, что даже если одна из операций последовательности является дорогостоящей, то при усреднении по всем операциям средняя их стоимость будет небольшой.
Амортизационный анализ использует следующие методы:
1. Метод средних (метод группового анализа).
2. Метод предоплаты (метод бухгалтерского учета).
3. Метод потенциалов.

Метод средних (метод группового анализа)

Определим [math]t_1,t_2, ... t_n[/math] - время выполнения операций [math]1,2, ... , n.[/math]
В методе средних амортизированная стоимость операций определяется следующим образом: суммарная стоимость всех операций алгоритма делится на их количество, т.е. [math]\frac{\sum^{n}_{i=1} {t_i}}{n}[/math]. При этом каждой операции присвается одна и та же средняя амортизированная стоимость.

Рассмотрим стек с операцией [math]multipop(a)[/math] - извлечение из стека [math]a[/math] элементов. В худшем случае она работает за [math]O(n)[/math] времени, если удаляются все элементы массива. Однако прежде чем удалить элемент, его нужно добавить в стек. Итак, если в стеке было не более [math]n[/math] элементов, то в худшем случае с каждым из них могли быть произведены 2 операции - добавление в стек и извлечение из него. Например, если было [math]n[/math] операций [math]push[/math] - добавление в стек, стоимость каждой [math]O(1)[/math], и одна операция [math]multipop(n)[/math], то суммарное время всех операций - [math]O(2n)[/math], всего операций [math]n+1[/math], а значит, амортизационная стоимость операции - [math]O(1)[/math].

Метод предоплаты (метод бухгалтерского учета)

Рассмотрим метод предоплаты на примере работы саморасширяющегося массива.
Пусть в массиве реализованы операции [math]push(x)[/math] - добавление элемента [math]x[/math] в последнюю незанятую ячейку массива, если она есть, и операция [math]add(x)[/math] - она выделяет память размером [math]2n[/math], если в массиве было [math]n[/math] элементов, и добавляет [math]x[/math] на [math]n+1[/math] место в новом массиве. Покажем, что амортизированная стоимость операции [math]add[/math] равна [math]0(1)[/math].
Представим, что использование определенного количества времени равносильно использованию определенного количества монет (плата за выполнение каждой операции). Перед использованием операции [math]add(x)[/math] программе необходимо выполнить [math]n[/math] операций [math]push(x)[/math]. Пусть на каждую операцию [math]push(x)[/math] тратися три монеты - одна на добавление элемента в массив, одну монету будем класть рядом с элементом на место [math]i[/math], и еще одну на [math]i/2[/math] место в массиве (до первого выполнения операции [math]add(x)[/math] эта монета никуда не кладется). К тому моменту, как нам нужно будет выполнить операцию [math]add(x)[/math] около каждого элемента массива будет лежать по одной монете, которая и будет тратиться на его копирование во вновь созданный массив удвоенной длины. Таким образом, каждая операция [math]push(x)[/math] стоит три монеты, а каждая операция [math]add(x)[/math] ничего не стоит и произвродится за счет накопленных ранее монет, т.е. ее амортизированная стоимость равна [math]O(1)[/math], что и требовалось доказать.

Литература

Томас Кормен. Алгоритмы. Построение и анализ. - Санкт-Петербург, 2005. стр. 483-491.