80
правок
Изменения
Новая страница: «==Основные определения== {{Определение | 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.
{{Определение | 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.
