Изменения

'''Средняя амортизационная стоимость операций''' {{---}} величина <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>multipop(a)</tex> {{---}} извлечение из стека <tex>a</tex> элементов. В худшем случае она работает за <tex>O(n)</tex> времени, если удаляются все элементы массива. Однако прежде чем удалить элемент, его нужно добавить в стек. Итак, если в стеке было не более <tex>n</tex> элементов, то в худшем случае с каждым из них могли быть произведены 2 операции - добавление в стек и извлечение из него. Например, если было <tex>n</tex> операций <tex>push</tex> - добавление в стек, стоимость каждой <tex>O(1)</tex>, и одна операция <tex>multipop(n)</tex>, то суммарное время всех операций {{---}} <tex>O(n)</tex>, всего операций <tex>n + 1</tex>, а значит, амортизационная стоимость операции {{---}} <tex>O(1)</tex>.

Пусть Рассмотрим стек с операцией <tex>\mathrm{multipop}{(a)}</tex> {{---}} извлечение из стека <tex>a</tex> элементов. В худшем случае она работает за <tex>O(n)</tex> времени, если удаляются все элементы массива. Однако прежде чем удалить элемент, его нужно добавить в стек. Итак, если в стеке было не более <tex>n</tex> элементов, то в худшем случае с каждым из них могли быть произведены две операции {{---}} количество добавление в стек и извлечение из него. Например, если было <tex>n</tex> операций<tex>\mathrm{push}{}</tex> {{---}} добавление в стек, стоимость каждой <tex>mO(1)</tex> , и одна операция <tex>\mathrm{multipop}{(n)}</tex>, то суммарное время всех операций {{---}} количество элементов<tex>O(n)</tex>, задействованных в этих операциях. Очевидно всего операций <tex>m \leq n+ 1</tex>, а значит, амортизационная стоимость операции {{---}} <tex>O(1)</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{}{}{}{}{\fracsum\limits^{2mn}_{i=1} {t_i}}{n} = \leq 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> , так как над элементом можно совершить только две операции, стоимость которых равна <tex>m \leq n1</tex>{{---}} добавление и удаление.Тогда:

<tex dpi = "150">a \leqslant \genfrac{}{}{}{}{2m}{n} \leqslant 2,</tex> так как <tex>m \leqslant n</tex>. Таким образом, cредняя средняя амортизационная стоимость операций <tex>a = O(1)</tex>. =====Двоичный счётчик=====Рассмотрим также двоичный инкрементальный счётчик (единственная возможная операция {{---}} увеличить значение на единицу). Пусть результат увеличения счётчика {{---}} <tex>n</tex>, тогда в худшем случае необходимо изменить значения <tex> 1 + \lfloor \log n \rfloor</tex> бит, тогда стоимость <tex>n</tex> операций {{---}} <tex> O(n \log n) </tex>.Теперь воспользуемся для анализа методом усреднения.Каждый следующий бит изменяет своё значение в <tex dpi = "150">n, \genfrac{}{}{}{}{n}{2}, \genfrac{}{}{}{}{n}{4} \dots</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 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>

====ПримерПримеры====В качестве примера вновь рассмотрим стек с операцией <tex>multipop(a)</tex>. Пусть потенциал {{---}} это количество элементов в стеке. Тогда:

1.1) =====Стек с multipop=====В качестве примера вновь рассмотрим стек с операцией <tex>a_\mathrm{multipop}{push(a)} = 1 + 1 = 2,</tex> т. к. время выполнения операции <tex>push</tex> {{---}} 1, и изменение потенциала Пусть потенциал {{---}} тоже 1это количество элементов в стеке.Тогда:

# Амортизированная стоимость операций:#* <tex>a_{push} = 1 + 1 = 2,</tex> так как время выполнения операции <tex>\mathrm{push}{}</tex> {{---}} <tex>1</tex>, и изменение потенциала {{---}} тоже <tex>1</tex>.2) #* <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>

1.3) Таким образом, <tex>a_{multipop} f(n, m) = k - k = 0,1</tex> т. к. время выполнения операции , а значит, средняя амортизационная стоимость операций <tex>multipopa = O(k1)</tex> {{---}} k, а изменение потенциала {{---}} -k.

2) Для любого <tex>i: \enskip \Phi_i = O(n),</tex> так как элементов в стеке не может быть больше <tex>n</tex>====Динамические хэш-таблицы=====

Таким образомРассмотрим хэш-таблицы, использующие цепочки для разрешения коллизий. Для того, чтобы поиск элемента в цепочке не начал слишком сильно влиять на производительность, введём величину <tex>f\alpha </tex> {{---}} фактор загруженности (load factor) нашей таблицы.Пусть в нашей таблице размером <tex> m </tex> хранится <tex> n</tex> элементов, тогда <tex dpi = "150"> \alpha = \genfrac{}{}{}{}{n}{m} </tex>Введём значение <tex>\alpha_{max}</tex>, при превышении которого таблица будет пересоздана с увеличением размера и все элементы будут перераспределены по-новому (rehashing).Из-за этого сложность операции <tex>\mathrm{add}{}</tex> из <tex> O(1) </tex> станет в худшем случае <tex> O(n) </tex>, так как для пересоздания таблицы нам требуется <tex> O(n) </tex> операций.Стоит отметить, что изменение размера массива всегда должно быть геометрическим (в <tex> k </tex> раз), потому как при изменении размера на константу нам потребуется <tex>O(n) </tex> раз пересоздать таблицу, что приведёт к сложности операции <tex>\mathrm{add}{}</tex> в <tex> O(n^2) </tex>. Введём такую потенциальную функцию, что она будет "запасать" время по мере удаления фактора загруженности от <tex dpi = "150">\genfrac{}{}{}{}{1}{2}</tex>:<tex> \Phi = 2|{n - m/2}| </tex>Предположим, не умаляя общности, что <tex>\alpha_{max} = 1</tex>.Теперь рассмотрим все возможные случаи для каждой из операций <tex>add, а значитremove, cредняя 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>.#*<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>, если вместо списков использовать сбалансированные деревья поиска (например, в <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, следовательно амортизированное время {{---}} <tex>1 + 2 = 3</tex>.  В каждом случае амортизированное время одной операции в среднем случае {{---}} <tex>O(1)</tex>, в худшем случае {{---}} <tex>O(n)</tex>. Если мы создадим нашу таблицу так, что <tex dpi = "150">\alpha = \genfrac{}{}{}{}{1}{2}</tex>, то изначально потенциал будет равен нулю. И так мы будем знать, что потенциал никогда не станет меньше этого значения; в итоге амортизированная стоимость будет верхней границей реальной оценки. Следовательно, сложность последовательности из <tex>n</tex> операций в среднем случае будет равна <tex>a = O(1n)</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>. ====Примеры=========Стек с multipop=====При выполнении операции <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>multipop(a)n</tex>операций добавления элемента в очередь и операцию удаления последнего добавленного в очередь элемента. При выполнении операции Очевидно, это потребует <tex>pushO(n)</tex> будем использовать две монеты {{---}} одну для самой операциивремени в целом. Но известно, а вторую {{---}} что каждый элемент был добавлен в качестве резерва. Тогда для операций <tex>pop</tex> стеки и удалён из них не более <tex>multipop1</tex> учётную раза, следовательно, амортизированная стоимость можно принять равной нулю и использовать для удаления элемента монету, оставшуюся после каждой операции в нашей последовательности {{---}} <tex>pushO(1)</tex>.

Таким образом, для амортизационная стоимость каждой операции требуется для очереди {{---}} <tex>O(1)</tex> монет, а значит, cредняя амортизационная стоимость операций <tex>a .== O(1)</tex>См.также ==*[[Хеш-таблица]]

==ЛитератураИсточники информации==* Томас Кормен. Алгоритмы. Построение и анализ. - Санкт-Петербург, 2005. стр. 483-491.* [[wikipedia:Amortized_analysis | Wikipedia {{---}} Amortized analysis]]