Изменения
Нет описания правки
Такой анализ чаще всего используется, чтобы показать, что даже если некоторые из операций последовательности являются дорогостоящими, то при усреднении по всем операциям средняя их стоимость будет небольшой за счёт низкой частоты встречаемости. Подчеркнём, что оценка, даваемая амортизационным анализом, не является вероятностной: это оценка среднего времени выполнения операций для худшего случая.
{{Определение | definition =
'''Средняя амортизационная стоимость операций''' {{---}} величина <tex>a</tex>, находящаяся по формуле: <tex dpi = "150">a = \fracgenfrac{}{}{}{}{\sum\limits^{n}_{i = 1} {t_i}}{n}</tex>, где <tex>t_1,t_2, ... \dots t_n</tex> {{- --}} время выполнения операций <tex>1,2, ... , \dots n,</tex> , совершённых над структурой данных.
}}
Амортизационный анализ использует следующие методы:
====Примеры====
Распишем приведённые рассуждения более формально.Пусть <tex dpi = "150">a = \frac{\sum\limits^{n}_{i=1} {t_i}}{n} = \frac{\sum\limits^{n}_{i=1} \sum\limits^{m}_{j=1} {t_{ij}}}{n} = \frac{\sum\limits^{m}_{j=1} \sum\limits^{n}_{i=1} {t_{ij}}}{n},</tex> где <tex>{t_{ij}}</tex> {{---}} стоимость количество операций, <tex>im</tex>{{--ой операции над <tex>j</tex>-ым элементом}} количество элементов, задействованных в этих операциях. Величина Очевидно, <tex>m \sum\limits^{leqslant n}_{i=1} {t_{ij}}</tex> не превосходит 2, т. к. над элементом можно совершить только 2 операции, стоимость которых равна 1 {{---}} добавление и удаление. Тогда:
<texdpi = "150">a = \leq 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\fraclimits^{n}_{i=1} {t_{ij}}</tex> не превосходит <tex>2</tex>, так как над элементом можно совершить только две операции, стоимость которых равна <tex>1</tex> {{---}} добавление и удаление. Тогда: <tex dpi = "150">a \leqslant \genfrac{}{}{}{}{2m}{n} \leq leqslant 2,</tex> так как <tex>m \leq leqslant n</tex>.
Таким образом, средняя амортизационная стоимость операций <tex>a = O(1)</tex>.
=====Двоичный счётчик=====Рассмотрим также двоичный инкрементальный счётчик(единственная возможная операция {{- --}} увеличить значение на единицу). Пусть результат увеличения счётчика {{--- }} <tex>n</tex>, тогда в худшем случае необходимо изменить значения <tex> 1 + \lfloor \log n \rfloor</tex> бит, тогда стоимость <tex>n</tex> операций {{- --}} <tex> O(n \log n) </tex>.
Теперь воспользуемся для анализа методом усреднения.
Каждый следующий бит изменяет своё значение в <texdpi = "150">n, \genfrac{}{}{}{}{n/}{2}, \genfrac{}{}{}{}{n/}{4...} \dots</tex> операциях.Общая стоимость: <texdpi = "150"> \sum\limits_{i=0}^{\lfloor \log n \rfloor} \fracgenfrac{}{}{}{}{n}{2^i} < 2n = O(n)</tex>; <tex dpi = "150"> \genfrac{}{}{}{}{O(n)}{n} = O(1) </tex> В итоге амортизированная стоимость одной операции {{---}} <tex>O(1)</tex>.
==Метод потенциалов==
2) Для любого <tex>i: \enskip \Phi_i = O(n \relax f(n, m))</tex>
|proof =
<tex dpi = "150">a = \fracgenfrac{}{}{}{}{\sum\limits^{n}_{i = 1} {t_i}}{n} = \fracgenfrac{}{}{}{}{\sum\limits^{n}_{i = 1} {a_i} + \sum\limits^{n - 1}_{i = 0} {\Phi_i} - \sum\limits^{n}_{i = 1} {\Phi_i} }{n} = \fracgenfrac{}{}{}{}{n \relax O(f(n, m)) + \Phi_0 - \Phi_n}{n} = O(f(n, m))</tex>
}}
====ПримерПримеры==== =====Стек с multipop=====В качестве примера вновь рассмотрим стек с операцией <tex>\mathrm{multipop}{(a)}</tex>. Пусть потенциал {{---}} это количество элементов в стеке. Тогда: # Амортизированная стоимость операций:#* <tex>a_{push} = 1 + 1 = 2,</tex> так как время выполнения операции <tex>\mathrm{push}{}</tex> {{---}} <tex>1</tex>, и изменение потенциала {{---}} тоже <tex>1</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 dpi = "150">\genfrac{}{}{}{}{1}{2}</tex>:<tex> \Phi = 2|{n - m/2}| </tex>Предположим, не умаляя общности, что <tex>\alpha_{max} = 1</tex>.Теперь рассмотрим все возможные случаи для каждой из операций <tex>add, remove, find</tex>.#<tex>\mathrm{add}{}</tex>: <tex>\, n</tex> увеличивается на единицу. Следовательно, имеются три случая:#*<tex dpi = "150">\genfrac{}{}{}{}{1}{2} \leqslant \alpha < 1 </tex>: потенциал увеличивается на <tex>2</tex>, следовательно амортизированное время {{---}} <tex>1 + 2 = 3) </tex>.#*<texdpi = "150">a_\alpha < \genfrac{}{}{}{}{1}{multipop2} </tex>: потенциал уменьшается на <tex>2</tex>, и амортизированное время <tex> 1 - 2 = k - k 1 </tex>.#*<tex>\alpha = 01</tex>: Таблица увеличивается в размере,так что реальная сложность {{---}} <tex> 1 + m </tex> т. кНо потенциал изменяется с <tex>m</tex> до нуля, следовательно амортизационная сложность {{---}} <tex> 1 + m - m = 1</tex>. #<tex>\mathrm{find}{}</tex>: Рассмотрим два случая:#* Элементы распределяются по таблице достаточно равномерно: время выполнения операции поиска элемента в списке {{---}} <tex>multipopO(k1)</tex> , потенциал не изменяется, следовательно и реальная, и амортизированная сложности {{---}} k<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 dpi = "150">\genfrac{}{}{}{}{1}{2} \leqslant \alpha </tex>: потенциал уменьшается на 2, и амортизированное время <tex> 1 - 2 = -1 </tex>.#*<tex dpi = "150">\alpha < \genfrac{}{}{}{}{1}{2}</tex>: потенциал увеличивается на 2, а изменение потенциала следовательно амортизированное время {{---}} -k<tex>1 + 2 = 3</tex>.
==Метод предоплаты==
Представим, что использование определенного количества времени равносильно использованию определенного количества монет (плата за выполнение каждой операции). В методе предоплаты каждому типу операций присваивается своя учётная стоимость. Эта стоимость может быть больше фактической, в таком случае лишние монеты используются как резерв для выполнения других операций в будущем, а может быть меньше, тогда гарантируется, что текущего накопленного резерва достаточно для выполнения операции. Для доказательства оценки средней амортизационной стоимости <tex>O(f(n, m))</tex> нужно построить учётные стоимости так, что для каждой операции она будет составлять <tex>O(f(n, m))</tex>. Тогда для последовательности из <tex>n</tex> операций суммарно будет затрачено <tex>n \cdot O(f(n, m))</tex> монет, следовательно, cредняя амортизационная стоимость операций будет <tex dpi = "150">a = \fracgenfrac{}{}{}{}{\sum\limits^{n}_{i = 1} {t_i}}{n} = \fracgenfrac{}{}{}{}{n \cdot O(f(n, m))}{n}</tex> <tex>= O(f(n, m))</tex>.
====ПримерПримеры====Опять же рассмотрим стек =====Стек с операцией <tex>multipop(a)</tex>. =====При выполнении операции <tex>\mathrm{push}{}</tex> будем использовать две монеты {{---}} одну для самой операции, а вторую {{---}} в качестве резерва. Тогда для операций <tex>\mathrm{pop}{}</tex> и <tex>\mathrm{multipop}{}</tex> учётную стоимость можно принять равной нулю и использовать для удаления элемента монету, оставшуюся после операции <tex>\mathrm{push}{}</tex>.
Таким образом, для каждой операции требуется <tex>O(1)</tex> монет, а значит, средняя амортизационная стоимость операций <tex>a = O(1)</tex>.
==Литература===Очередь на двух стеках===== Рассмотрим реализацию очереди на двух стеках. Пусть наши стеки имеют операции <tex>\mathrm{push}{}</tex> и <tex>\mathrm{pop}{}</tex>, обе стоимостью <tex>1</tex>.Пусть каждое добавление элемента в очередь будет стоить <tex>3</tex> монеты, стоимость удаления элемента из очереди {{---}} <tex>1</tex> монета. В лучшем случае(последовательность операций {{---}} добавить элемент и сразу же удалить его из очереди) мы тратим по монете непосредственно на <tex>\mathrm{push}{}</tex> в оба стека и <tex>\mathrm{pop}{}</tex> из первого стека, а стоимость удаления элемента из очереди непосредственно тратим на <tex>\mathrm{pop}{}</tex> из второго стека, и амортизированная сложность {{---}} <tex>O(1)</tex>. Рассмотрим другой случай. Предположим, мы имеем <tex>n</tex> операций добавления элемента в очередь и операцию удаления последнего добавленного в очередь элемента. Очевидно, это потребует <tex>O(n)</tex> времени в целом. Но известно, что каждый элемент был добавлен в стеки и удалён из них не более <tex>1</tex> раза, следовательно, амортизированная стоимость каждой операции в нашей последовательности {{---}} <tex>O(1)</tex>. Таким образом, амортизационная стоимость каждой операции для очереди {{---}} <tex> O(1) </tex>.== См. также ==*[[Хеш-таблица]] ==Источники информации==* Томас Кормен. Алгоритмы. Построение и анализ. - Санкт-Петербург, 2005. стр. 483-491.* [[wikipedia:Amortized_analysis | Wikipedia {{---}} Amortized analysis]]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Амортизационный анализ]]