13
правок
Изменения
м
1. #Метод усреднения (метод группового анализа). 2. #Метод потенциалов. 3. #Метод предоплаты (метод бухгалтерского учетаучёта).
1) #Для любого <tex>i: \enskip a_i = O(f(n, m))</tex>2) #Для любого <tex>i: \enskip \Phi_i = O(n \relax cdot f(n, m))</tex>
Поправка пунктуации. ("следовательно" здесь - вводное слово, а не союз)
==Основные определения==
{{Определение | definition =
'''Амортизационный анализ''' (англ. ''amortized analysis'') {{---}} метод подсчета подсчёта времени, требуемого для выполнения последовательности операций над структурой данных. При этом время усредняется по всем выполняемым операциям, и анализируется средняя производительность операций в худшем случае.
}}
Такой анализ чаще всего используется, чтобы показать, что даже если некоторые из операций последовательности являются дорогостоящими, то при усреднении по всем операциям средняя их стоимость будет небольшой за счёт низкой частоты встречаемости. Подчеркнём, что оценка, даваемая амортизационным анализом, не является вероятностной: это оценка среднего времени выполнения операций для худшего случая.
}}
Амортизационный анализ использует следующие методы:
==Метод усреднения==
О методе потенциалов
|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> если выполнены два условия:
|proof =
<tex dpi = "150">a = \genfrac{}{}{}{}{\sum\limits^{n}_{i = 1} {t_i}}{n} = \genfrac{}{}{}{}{\sum\limits^{n}_{i = 1} {a_i} + \sum\limits^{n - 1}_{i = 0} {\Phi_i} - \sum\limits^{n}_{i = 1} {\Phi_i} }{n} = \genfrac{}{}{}{}{n \relax cdot O(f(n, m)) + \Phi_0 - \Phi_n}{n} = O(f(n, m))</tex>
}}
#* <tex>a_{pop} = 1 - 1 = 0,</tex> так как время выполнения операции <tex>\mathrm{pop}{}</tex> {{---}} <tex>1</tex>, а изменение потенциала {{---}} <tex>-1</tex>.
#* <tex>a_{multipop} = k - k = 0,</tex> так как время выполнения операции <tex>\mathrm{multipop}{(k)}</tex> {{---}} <tex>k</tex>, а изменение потенциала {{---}} <tex>-k</tex>.
# Для любого <tex>i: \enskip \Phi_i = O(n),</tex> так как элементов в стеке не может быть больше <tex>n</tex>
Таким образом, <tex>f(n, m) = 1</tex>, а значит, средняя амортизационная стоимость операций <tex>a = O(1)</tex>.
#*<tex>\alpha = \alpha_{max} : a_i = 1 + \alpha_{max}m + 2 \cdot (\alpha_{max} m + 1) - 2\alpha_{max} m - 2 \alpha_{max} m + \alpha_{max} m = 3 </tex>, так как таблица увеличивается в размере, поэтому время работы операции <tex> \mathrm{add} </tex> составит <tex> 1 + \alpha_{max}m </tex>, потому что сейчас в таблице <tex> n = \alpha_{max} m </tex> элементов.
# <tex>\mathrm{find}{}</tex>:
#* Если элементы распределяются по таблице достаточно равномерно, то время поиска элемента в списке {{---}} <tex>O(1)</tex>, потенциал не изменяется, следовательно , и реальная, и амортизированная сложности {{---}} <tex>1</tex>.
#* В случае, если все элементы оказываются размещены в одном списке, время поиска элемента достигает <tex>O(n)</tex>. Это время может быть улучшено до <tex>O(\log n)</tex>, если вместо списков использовать сбалансированные [[Дерево поиска, наивная реализация | деревья поиска]] (эта модификация была добавлена в <tex>\mathrm{Java\ 8}{}</tex> для стандартной коллекции <tex>\mathrm{HashSet}</tex>).
#<tex>\mathrm{remove}{}</tex>: <tex> n</tex> уменьшается на единицу. Тогда амортизационное время работы с учётом изменения потенциала составит:
==Метод предоплаты==
Представим, что использование определенного определённого количества времени равносильно использованию определенного определённого количества монет (плата за выполнение каждой операции). В методе предоплаты каждому типу операций присваивается своя учётная стоимость. Эта стоимость может быть больше фактической, в таком случае лишние монеты используются как резерв для выполнения других операций в будущем, а может быть меньше, тогда гарантируется, что текущего накопленного резерва достаточно для выполнения операции. Для доказательства оценки средней амортизационной стоимости <tex>O(f(n, m))</tex> нужно построить учётные стоимости так, что для каждой операции она будет составлять <tex>O(f(n, m))</tex>. Тогда для последовательности из <tex>n</tex> операций суммарно будет затрачено <tex>n \cdot O(f(n, m))</tex> монет, следовательно, средняя амортизационная стоимость операций будет <tex dpi = "150">a = \genfrac{}{}{}{}{\sum\limits^{n}_{i = 1} {t_i}}{n} = \genfrac{}{}{}{}{n \cdot O(f(n, m))}{n}</tex> <tex>= O(f(n, m))</tex>.
====Примеры====
