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

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

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

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

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

Литература

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