Изменения
Нет описания правки
Таким образом, средняя амортизационная стоимость операций <tex>a = O(1)</tex>.
Рассмотрим также двоичный инкрементальный счётчик(единственная возможная операция - увеличить значение на единицу).
}}
====ПримерПримеры====
В качестве примера вновь рассмотрим стек с операцией <tex>multipop(a)</tex>. Пусть потенциал {{---}} это количество элементов в стеке. Тогда:
Таким образом, <tex>f(n, m) = 1</tex>, а значит, средняя амортизационная стоимость операций <tex>a = O(1)</tex>.
Рассмотрим хэш-таблицы, использующие цепочки для разрешения коллизий. Для того, чтобы поиск элемента в цепочке не начал слишком сильно влиять на производительность, введём величину <tex> \alpha </tex> - фактор загруженности(load factor) нашей таблицы.
Пусть в нашей таблице размером <tex> m </tex> хранится <tex> n </tex> элементов, тогда <tex> \alpha = \frac{n}{m} </tex>
Введём значение <tex>\alpha_{max}</tex>, при превышении которого таблица будет пересоздана с увеличением размера и все элементы будут перераспределены по-новому(rehashing). Аналогично будем пересоздавать таблицу с уменьшением размера при удалении элемента.
Из-за этого сложность операции <tex>add</tex> из <tex> O(1) </tex> станет в худшем случае <tex> O(n) </tex>, так как для пересоздания таблицы нам требуется <tex> O(n) </tex> операций.
Стоит отметить, что изменение размера массива всегда должно быть геометрическим(в <tex> k </tex> раз), потому как при изменении размера на константу нам потребуется <tex>O(n)</tex> раз пересоздать таблицу, что приведёт к сложности операции <tex>add</tex> в <tex> O(n^2) </tex>.
Введём такую потенциальную функцию, что она будет "запасать" время по мере удаления фактора загруженности от <tex>\frac{1}{2}</tex>:
<tex> \phi = 2|{n - m/2}| </tex>
Предположим, не умаляя общности, что<tex>\alpha_{max} = 1</tex>.
Теперь рассмотрим все возможные случаи для каждой из операций <tex>add, remove, find</tex>.
Операция <tex>add: n</tex> увеличивается на единицу. Следовательно, имеются три случая:
<tex>\frac{1}{2} \leq \alpha < 1 </tex>: потенциал увеличивается на 2, следовательно амортизированное время - <tex>1 + 2 = 3</tex>.
<tex>\alpha < \frac{1}{2}</tex>: потенциал уменьшается на 2, и амортизированное время <tex> 1 - 2 = -1 </tex>.
<tex>\alpha = 1</tex>: Таблица увеличивается в размере, так что реальная сложность - <tex> 1 + m </tex>. Но потенциал изменяется с <tex>m</tex> до нуля, следовательно амортизационная сложность - <tex> 1 + m - m = 1</tex>.
<tex>find:</tex> Потенциал не изменяется, следовательно и реальная, и амортизированная сложности - <tex>1</tex>.
<tex>remove: n</tex> уменьшается на единицу. Возможны три случая:
<tex>\frac{1}{2} \leq \alpha < 1 </tex>: потенциал уменьшается на 2, и амортизированное время <tex> 1 - 2 = -1 </tex>.
<tex>\alpha < \frac{1}{2}</tex>: потенциал увеличивается на 2, следовательно амортизированное время - <tex>1 + 2 = 3</tex>.
<tex>\alpha = 1</tex>: Таблица уменьшается в размере, следовательно реальная сложность - <tex> 1 + \frac{m}{4}</tex>, а потенциал меняется от <tex>\frac{m}{2}</tex> до нуля, следовательно амортизированная стоимость - <tex> 1 + \frac{m}{4} - \frac{m}{2} = 1 - \frac{m}{4}</tex>.
В каждом случае амортизированное время одной операции - <tex>O(1)</tex>. Если мы создадим нашу таблицу так, что <tex>\alpha = \frac{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 = "150">a = \frac{\sum\limits^{n}_{i = 1} {t_i}}{n} = \frac{n \cdot O(f(n, m))}{n}</tex> <tex>= O(f(n, m))</tex>.
====ПримерПримеры====
Опять же рассмотрим стек с операцией <tex>multipop(a)</tex>. При выполнении операции <tex>push</tex> будем использовать две монеты {{---}} одну для самой операции, а вторую {{---}} в качестве резерва. Тогда для операций <tex>pop</tex> и <tex>multipop</tex> учётную стоимость можно принять равной нулю и использовать для удаления элемента монету, оставшуюся после операции <tex>push</tex>.
Таким образом, для каждой операции требуется <tex>O(1)</tex> монет, а значит, средняя амортизационная стоимость операций <tex>a = O(1)</tex>.
Рассмотрим реализацию очереди на двух стеках. Пусть наши стеки имеют операции <tex>push</tex> и <tex>pop</tex>, обе стоимостью <tex>1</tex>.
Пусть каждое добавление элемента в очередь будет стоить 3 монеты. Это покроет стоимость операций <tex>push</tex> и <tex>pop</tex> для переноса элемента из первого стека во второй, если потребуется, и ещё 1 монета будет нужна для того, чтобы поместить элемент в первый стек. Стоимость удаления элемента из очереди - 1 монета(она потребуется нам для удаления элемента из второго стека).
Таким образом, амортизационная стоимость каждой операции - <tex> O(1) </tex>.
==Литература==
