Изменения

Перейти к: навигация, поиск

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

2881 байт добавлено, 03:28, 15 марта 2011
Новая страница: «==Основные определения== {{Определение | definition = '''Амортизационный анализ''' - метод подсчета …»
==Основные определения==
{{Определение | definition =
'''Амортизационный анализ''' - метод подсчета времени, требуемого для выполнения последовательности операций над структурой данных. При этом время усредняется по всем выполняемым операциям и гарантируется средняя производительность операций в наихудшем случае.
}}
Такой анализ чаще всего используется, чтобы показать, что даже если одна из операций последовательности является дорогостоящей, то при усреднении по всем операциям средняя их стоимость будет небольшой.
<br>
Амортизационный анализ использует следующие методы:
<br>
1. Метод средних (метод группового анализа).<br>
2. Метод предоплаты (метод бухгалтерского учета).<br>
3. Метод потенциалов.<br>

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

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

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

Рассмотрим метод предоплаты на примере работы саморасширяющегося массива.
Пусть в массиве реализована операция <tex>add(x)</tex> - добавление элемента <tex>x</tex> в последнюю незанятую ячейку массива, если она есть, в противном случае эта операция выделяет память размером <tex>2n</tex>, если в массиве было <tex>n</tex> элементов, и добавляет <tex>x</tex> на <tex>n+1</tex> место в массиве.


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

Навигация