Изменения

'''Амортизационный анализ''' (англ. ''amortized analysis'') {{---}} метод подсчета подсчёта времени, требуемого для выполнения последовательности операций над структурой данных. При этом время усредняется по всем выполняемым операциям, и анализируется средняя производительность операций в худшем случае.

 1. #Метод усреднения (метод группового анализа). 2. #Метод потенциалов. 3. #Метод предоплаты (метод бухгалтерского учетаучёта).

Рассмотрим [[Стек | стек ]] с операцией <tex>\mathrm{multipop}{(a)}</tex> {{---}} извлечение из стека <tex>a</tex> элементов. В худшем случае она работает за <tex>O(n)</tex> времени, если удаляются все элементы массива. Однако прежде чем удалить элемент, его нужно добавить в стек. Итак, если в стеке было не более <tex>n</tex> элементов, то в худшем случае с каждым из них могли быть произведены две операции {{---}} добавление в стек и извлечение из него. Например, если было <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>\Phi</tex> {{---}} потенциал. Изначально потенциал равен <tex>\Phi_0</tex>, а после выполнения <tex>i</tex>-ой й операции {{---}} <tex>\Phi_i</tex>. Стоимость <tex>i</tex>-ой й операции обозначим <tex>a_i = t_i + \Phi_i - \Phi_{i-1}</tex>. Пусть <tex>n</tex> {{---}} количество операций, <tex>m</tex> {{---}} размер структуры данных. Тогда средняя амортизационная стоимость операций <tex>a = O(f(n, m)),</tex> если выполнены два условия:

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

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

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

#*<tex> \alpha < \alpha_{max} : \alpha_i = 1 + 2 \cdot (n + 1) - \alpha_{max} m + - (2n - \alpha_{max} m ) = 3</tex>, так как время выполнения операции <tex> \mathrm{add} </tex> {{---}} <tex> 1 </tex>

#* <tex> a_{remove} = 1 + 2 \cdot (n - 1) - \alpha_{max} m + - (2n - \alpha_{max} m ) = -1 </tex>

Представим, что использование определенного определённого количества времени равносильно использованию определенного определённого количества монет (плата за выполнение каждой операции). В методе предоплаты каждому типу операций присваивается своя учётная стоимость. Эта стоимость может быть больше фактической, в таком случае лишние монеты используются как резерв для выполнения других операций в будущем, а может быть меньше, тогда гарантируется, что текущего накопленного резерва достаточно для выполнения операции. Для доказательства оценки средней амортизационной стоимости <tex>O(f(n, m))</tex> нужно построить учётные стоимости так, что для каждой операции она будет составлять <tex>O(f(n, m))</tex>. Тогда для последовательности из <tex>n</tex> операций суммарно будет затрачено <tex>n \cdot O(f(n, m))</tex> монет, следовательно, средняя амортизационная стоимость операций будет <tex dpi = "150">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>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>\mathrm{push}{}</tex> и <tex>\mathrm{pop}{}</tex> с элементом в каждом стеке), следовательно, амортизированная стоимость каждой операции в нашей последовательности {{---}} <tex>O(1)</tex>. Таким образом, амортизационная стоимость каждой операции для очереди {{---}} <tex> O(1) </tex>. == См. также ==*[[Хеш-таблица]]