Изменения

Рассмотрим стек с операцией <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 dpi = "130150">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> не превосходит 2, т. к. над элементом можно совершить только 2 операции, стоимость которых равна 1 {{---}} добавление и удаление. Тогда:

<tex dpi = "130150">a \leqslant \genfrac{}{}{}{}{2m}{n} \leqslant 2,</tex> так как <tex>m \leqslant n</tex>.

Рассмотрим также двоичный инкрементальный счётчик (единственная возможная операция {{- --}} увеличить значение на единицу). Пусть результат увеличения счётчика {{--- }} <tex>n</tex>, тогда в худшем случае необходимо изменить значения <tex> 1 + \lfloor \log n \rfloor</tex> бит, тогда стоимость <tex>n</tex> операций {{--- }} <tex> O(n \log n) </tex>.

Каждый следующий бит изменяет своё значение в <tex dpi = "130150">n, \genfrac{}{}{}{}{n}{2}, \genfrac{}{}{}{}{n}{4} \dots</tex> операциях.Общая стоимость: <tex dpi = "130150"> \sum\limits_{i=0}^{\lfloor \log n \rfloor} \genfrac{}{}{}{}{n}{2^i} < 2n = O(n)</tex>;

<tex dpi = "130150"> \genfrac{}{}{}{}{O(n)}{n} = O(1) </tex>;В итоге амортизированная стоимость одной операции {{--- }} <tex>O(1)</tex>.

<tex dpi = "130150">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 O(f(n, m)) + \Phi_0 - \Phi_n}{n} = O(f(n, m))</tex>

Пусть в нашей таблице размером <tex> m </tex> хранится <tex> n </tex> элементов, тогда <tex dpi = "130150"> \alpha = \genfrac{}{}{}{}{n}{m} </tex>Введём значение <tex>\alpha_{max}</tex>, при превышении которого таблица будет пересоздана с увеличением размера и все элементы будут перераспределены по-новому (rehashing). Аналогично будем пересоздавать таблицу с уменьшением размера при удалении элемента.

Введём такую потенциальную функцию, что она будет "запасать" время по мере удаления фактора загруженности от <tex dpi = "130150">\genfrac{}{}{}{}{1}{2}</tex>:

##<tex dpi = "130150">\genfrac{}{}{}{}{1}{2} \leqslant \alpha < 1 </tex>: потенциал увеличивается на 2, следовательно амортизированное время {{---}} <tex>1 + 2 = 3</tex>.##<tex dpi = "130150">\alpha < \genfrac{}{}{}{}{1}{2}</tex>: потенциал уменьшается на 2, и амортизированное время <tex> 1 - 2 = -1 </tex>.

##<tex dpi = "130150">\genfrac{}{}{}{}{1}{2} \leqslant \alpha < 1 </tex>: потенциал уменьшается на 2, и амортизированное время <tex> 1 - 2 = -1 </tex>.##<tex dpi = "130150">\alpha < \leqslant \genfrac{}{}{}{}{1}{2}</tex>: потенциал увеличивается на 2, следовательно амортизированное время {{---}} <tex>1 + 2 = 3</tex>.##<tex>\alpha = 1</tex>: Таблица уменьшается в размере, следовательно реальная сложность {{---}} <tex dpi = "130"> 1 + \genfrac{}{}{}{}{m}{4}</tex>, а потенциал меняется от <tex dpi = "130">\genfrac{}{}{}{}{m}{2}</tex> до нуля, следовательно амортизированная стоимость {{---}} <tex dpi = "130"> 1 + \genfrac{}{}{}{}{m}{4} - \genfrac{}{}{}{}{m}{2} = 1 - \genfrac{}{}{}{}{m}{4}</tex>.

Если мы создадим нашу таблицу так, что <tex dpi = "130150">\alpha = \genfrac{}{}{}{}{1}{2}</tex>, то изначально потенциал будет равен нулю. И так мы будем знать, что потенциал никогда не станет меньше этого значения; в итоге амортизированная стоимость будет верхней границей реальной оценки. Следовательно, сложность последовательности из <tex>n</tex> операций в среднем случае будет равна <tex>O(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> монет, следовательно, cредняя амортизационная стоимость операций будет <tex dpi = "130150">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>.

Пусть каждое добавление элемента в очередь будет стоить <tex>3 </tex> монеты, стоимость удаления элемента из очереди {{---}} <tex>1 </tex> монета.

Рассмотрим другой случай. Предположим, мы имеем <tex>n</tex> операций добавления элемента в очередь и операцию удаления последнего добавленного в очередь элемента. Очевидно, это потребует <tex>O(n)</tex> времени в целом. Но известно, что каждый элемент был добавлен в стеки и удалён из них не более <tex>1 </tex> раза, следовательно, амортизированная стоимость каждой операции в нашей последовательности {{---}} <tex>O(1)</tex>.