Изменения
Нет описания правки
Такой анализ чаще всего используется, чтобы показать, что даже если некоторые из операций последовательности являются дорогостоящими, то при усреднении по всем операциям средняя их стоимость будет небольшой за счёт низкой частоты встречаемости. Подчеркнём, что оценка, даваемая амортизационным анализом, не является вероятностной: это оценка среднего времени выполнения операций для худшего случая.
{{Определение | definition =
'''Средняя амортизационная стоимость операций''' {{---}} величина <tex>a</tex>, находящаяся по формуле: <tex dpi = 150>a = \genfrac{}{}{}{}{\sum\limits^{n}_{i = 1} {t_i}}{n}</tex>, где <tex>t_1,t_2 \dots t_n</tex> {{- --}} время выполнения операций <tex>1,2 \dots n</tex>, совершённых над структурой данных.
}}
Амортизационный анализ использует следующие методы:
=====Стек с multipop=====
Рассмотрим стек с операцией <tex>\mathrm{multipop}{(a)}</tex> {{---}} извлечение из стека <tex>a</tex> элементов. В худшем случае она работает за <tex>O(n)</tex> времени, если удаляются все элементы массива. Однако прежде чем удалить элемент, его нужно добавить в стек. Итак, если в стеке было не более <tex>n</tex> элементов, то в худшем случае с каждым из них могли быть произведены 2 две операции {{---}} добавление в стек и извлечение из него. Например, если было <tex>n</tex> операций <tex>\mathrm{push}{}</tex> {{---}} добавление в стек, стоимость каждой <tex>O(1)</tex>, и одна операция <tex>\mathrm{multipop}{(n)}</tex>, то суммарное время всех операций {{---}} <tex>O(n)</tex>, всего операций <tex>n + 1</tex>, а значит, амортизационная стоимость операции {{---}} <tex>O(1)</tex>.
Распишем приведённые рассуждения более формально.
Пусть <tex>n</tex> {{---}} количество операций, <tex>m</tex> {{---}} количество элементов, задействованных в этих операциях. Очевидно, <tex>m \leqslant n</tex> Тогда:
<tex dpi = "150">a = \genfrac{}{}{}{}{\sum\limits^{n}_{i=1} {t_i}}{n} = \genfrac{}{}{}{}{\sum\limits^{n}_{i=1} \sum\limits^{m}_{j=1} {t_{ij}}}{n} = \genfrac{}{}{}{}{\sum\limits^{m}_{j=1} \sum\limits^{n}_{i=1} {t_{ij}}}{n},</tex> где <tex>{t_{ij}}</tex> {{---}} стоимость <tex>i</tex>-ой операции над <tex>j</tex>-ым элементом. Величина <tex>\sum\limits^{n}_{i=1} {t_{ij}}</tex> не превосходит <tex>2</tex>, т. к. над элементом можно совершить только 2 две операции, стоимость которых равна <tex>1 </tex> {{---}} добавление и удаление. Тогда:
<tex dpi = "150">a \leqslant \genfrac{}{}{}{}{2m}{n} \leqslant 2,</tex> так как <tex>m \leqslant n</tex>.
Общая стоимость: <tex dpi = "150"> \sum\limits_{i=0}^{\lfloor \log n \rfloor} \genfrac{}{}{}{}{n}{2^i} < 2n = O(n)</tex>;
<tex dpi = "150"> \genfrac{}{}{}{}{O(n)}{n} = O(1) </tex>;
В итоге амортизированная стоимость одной операции {{---}} <tex>O(1)</tex>.
В качестве примера вновь рассмотрим стек с операцией <tex>\mathrm{multipop}{(a)}</tex>. Пусть потенциал {{---}} это количество элементов в стеке. Тогда:
## <tex>a_{push} = 1 + 1 = 2,</tex> т. к. время выполнения операции <tex>\mathrm{push}{}</tex> {{---}} <tex>1</tex>, и изменение потенциала {{---}} тоже 1.## <tex>a_{pop} = 1 - 1 = 0,</tex> т. к. время выполнения операции <tex>\mathrm{pop}{}</tex> {{---}} <tex>1</tex>, а изменение потенциала {{---}} -1.## <tex>a_{multipop} = k - k = 0,</tex> т. к. время выполнения операции <tex>\mathrm{multipop}{(k)}</tex> {{---}} <tex>k</tex>, а изменение потенциала {{---}} -k.
# Для любого <tex>i: \enskip \Phi_i = O(n),</tex> так как элементов в стеке не может быть больше <tex>n</tex>
Предположим, не умаляя общности, что <tex>\alpha_{max} = 1</tex>.
Теперь рассмотрим все возможные случаи для каждой из операций <tex>add, remove, find</tex>.
#Операция <tex>\mathrm{add}{}: n</tex> увеличивается на единицу. Следовательно, имеются три случая:##*<tex dpi = "150">\genfrac{}{}{}{}{1}{2} \leqslant \alpha < 1 </tex>: потенциал увеличивается на <tex>2</tex>, следовательно амортизированное время {{---}} <tex>1 + 2 = 3</tex>.##*<tex dpi = "150">\alpha < \genfrac{}{}{}{}{1}{2}</tex>: потенциал уменьшается на <tex>2</tex>, и амортизированное время <tex> 1 - 2 = -1 </tex>.##*<tex>\alpha = 1</tex>: Таблица увеличивается в размере, так что реальная сложность {{---}} <tex> 1 + m </tex>. Но потенциал изменяется с <tex>m</tex> до нуля, следовательно амортизационная сложность {{---}} <tex> 1 + m - m = 1</tex>.
#<tex>\mathrm{find}{}:</tex> Рассмотрим два случая:
## * Элементы распределяются по таблице достаточно равномерно: время поиска элемента в списке {{---}} <tex>O(1)</tex>, потенциал не изменяется, следовательно и реальная, и амортизированная сложности {{---}} <tex>1</tex>.## * В случае, если все элементы оказываются размещены в одном списке, время поиска элемента достигает <tex>O(n)</tex>. Это время может быть улучшено до <tex>O(\log n)</tex>, если вместо списков использовать сбалансированные деревья поиска(в Java 8 такая реализация HashSet используется по стандарту для данных, которые можно сравнить).
#<tex>\mathrm{remove}{}: n</tex> уменьшается на единицу. Возможны три случая:
##*<tex dpi = "150">\genfrac{}{}{}{}{1}{2} \leqslant \alpha < 1 </tex>: потенциал уменьшается на 2, и амортизированное время <tex> 1 - 2 = -1 </tex>.##*<tex dpi = "150">\alpha \leqslant \genfrac{}{}{}{}{1}{2}</tex>: потенциал увеличивается на 2, следовательно амортизированное время {{---}} <tex>1 + 2 = 3</tex>.
==Источники информации==
*Томас Кормен. Алгоритмы. Построение и анализ. - Санкт-Петербург, 2005. стр. 483-491. *[http://en.wikipedia.org/wiki/Amortized_analysis Amortized analysis - Wikipedia, the free encyclopedia]
*[http://en.wikipedia.org/wiki/Amortized_analysis Amortized analysis [Хеш- Wikipedia, the free encyclopediaтаблица]]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Амортизационный анализ]]
