Изменения

Рассмотрим стек с операцией <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(2n)</tex>, всего операций <tex>n+1</tex>, а значит, амортизационная стоимость операции {{--- }} <tex>O(1)</tex>.

Введём для каждого состояния структуры данных величину <tex>\phiPhi</tex> {{---}} потенциал. Изначально потенциал равен <tex>\phi_0Phi_0</tex>, а после выполнения <tex>i</tex>-ой операции {{---}} <tex>\phi_iPhi_i</tex>. Стоимость <tex>i</tex>-ой операции обозначим <tex>a_i = t_i + \phi_i Phi_i - \phi_Phi_{i-1}</tex>. Пусть <tex>n</tex> {{---}} количество операций, <tex>m</tex> {{---}} размер структуры данных. Тогда средняя амортизационная стоимость операций <tex>a = O(f(n, m)),</tex> если выполнены два условия:

2) Для любого <tex>i: \enskip \phi_i Phi_i = O(n \relax f(n, m))</tex>

<tex dpi = "150">a = \frac{\sum\limits^{n}_{i = 1} {t_i}}{n} = \frac{\sum\limits^{n}_{i = 1} {a_i} + \sum\limits^{n - 1}_{i = 0} {\phi_iPhi_i} - \sum\limits^{n}_{i = 1} {\phi_iPhi_i} }{n} = \frac{n \relax O(f(n, m)) + \phi_0 Phi_0 - \phi_nPhi_n}{n} = O(f(n, m))</tex>

1.1) <tex>a_{push} = 1 + 1 = 2,</tex> т. к. время выполнения операции <tex>push </tex> {{---}} 1, и изменение потенциала {{---}} тоже 1.

1.2) <tex>a_{pop} = 1 - 1 = 0,</tex> т. к. время выполнения операции <tex>pop </tex> {{---}} 1, а изменение потенциала {{---}} -1.

1.3) <tex>a_{multipop} = k - k = 0,</tex> т. к. время выполнения операции <tex>multipop(k) </tex> {{---}} k, а изменение потенциала {{---}} -k.

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

Рассмотрим метод предоплаты на примере работы саморасширяющегося массива.<br>====Пример====Пусть в массиве реализованы операции <tex>push(x)</tex> - добавление элемента <tex>x</tex> в последнюю незанятую ячейку массива, если она есть, и операция <tex>exp(x)</tex> (от "expansion") - она выделяет память размером <tex>2n</tex>, если в массиве было <tex>n</tex> элементов, и добавляет <tex>x</tex> на <tex>n+1</tex> место в новом массиве. Покажем, что амортизированная стоимость операции Опять же рассмотрим стек с операцией <tex>exp</tex> равна <tex>Omultipop(1a)</tex>.<br>Представим, что использование определенного количества времени равносильно использованию определенного количества монет (плата за выполнение каждой операции). Перед использованием При выполнении операции <tex>exp(x)</tex> программе необходимо выполнить <tex>n</tex> операций <tex>push(x)</tex>. Пусть на каждую операцию <tex>push(x)</tex> тратися три будем использовать две монеты {{--- одна на добавление элемента в массив, }} одну монету будем класть рядом с элементом на место <tex>i</tex>для самой операции, и еще одну на <tex>iа вторую {{---\frac{n}{2}</tex> место в массиве (до первого выполнения операции качестве резерва. Тогда для операций <tex>exp(x)pop</tex> эта монета никуда не кладется). К тому моменту, как нам нужно будет выполнить операцию и <tex>exp(x)multipop</tex> около каждого учётную стоимость можно принять равной нулю и использовать для удаления элемента массива будет лежать по одной монетемонету, которая и будет тратиться на его копирование во вновь созданный массив удвоенной длины. Таким образом, каждая операция оставшуюся после операции <tex>push(x)</tex> стоит три монеты. Таким образом, а каждая операция для каждой операции требуется <tex>expO(x1)</tex> ничего не стоит и произвродится за счет накопленных ранее монет, т.е. ее амортизированная а значит, cредняя амортизационная стоимость равна операций <tex>a = O(1)</tex>, что и требовалось доказать.