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

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

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

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

Такой анализ чаще всего используется, чтобы показать, что даже если одна из операций последовательности является дорогостоящей, то при усреднении по всем операциям средняя их стоимость будет небольшой.
Амортизационный анализ использует следующие методы:
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]add(x)[/math] - добавление элемента [math]x[/math] в последнюю незанятую ячейку массива, если она есть. В противном случае эта операция выделяет память размером [math]2n[/math], если в массиве было [math]n[/math] элементов, и добавляет [math]x[/math] на [math]n+1[/math] место в новом массиве. Покажем, что амортизированная стоимость операции [math]add[/math] равна трем.

Литература

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