170
правок
Изменения
Нет описания правки
Такой анализ чаще всего используется, чтобы показать, что даже если некоторые из операций последовательности являются дорогостоящими, то при усреднении по всем операциям средняя их стоимость будет небольшой за счёт низкой частоты встречаемости. Подчеркнём, что оценка, даваемая амортизационным анализом, не является вероятностной: это оценка среднего времени выполнения операций для худшего случая.
{{Определение | definition =
'''Средняя амортизационная стоимость операций''' {{---}} величина <tex>a</tex>, находящаяся по формуле: <tex dpi = "150">a = \frac{\sum\limits^{n}_{i=1} {t_i}}{n}</tex>, где <tex>t_1,t_2, ... t_n</tex> - время выполнения операций <tex>1,2, ... , n,</tex> совершённых над структурой данных.
}}
Амортизационный анализ использует следующие методы:
==Метод потенциалов==
{{Теорема
|about =
О методе потенциалов
|statement =
Введём для каждого состояния структуры данных величину <tex>\phi</tex> {{---}} потенциал. Изначально потенциал равен <tex>\phi_0</tex>, а после выполнения <tex>i</tex>-ой операции {{---}} <tex>\phi_i</tex>. Стоимость <tex>i</tex>-ой операции обозначим <tex>a_i = t_i + \phi_i - \phi_{i-1}</tex>. Пусть <tex>n</tex> {{---}} количество операций, <tex>m</tex> {{---}} размер структуры данных. Тогда средняя амортизационная стоимость операций <tex>a = O(f(n, m)),</tex> если выполнены два условия:
1) Для любого <tex>i: \enskip a_i = O(f(n, m))</tex>
2) Для любого <tex>i: \enskip \phi_i = O(n \relax f(n, m))</tex>
|proof =
<tex dpi = "150">a = \frac{\sum\limits^{n}_{i = 1} {t_i}}{n} = \frac{\sum\limits^{n}_{i = 1} {a_i} + \sum\limits^{n - 1}_{i = 0} {\phi_i} - \sum\limits^{n}_{i = 1} {\phi_i} }{n} = \frac{O(f(n, m)) * n + \phi_0 - \phi_n}{n} = O(f(n, m))</tex>
}}
====Пример====
==Метод предоплаты==
