Изменения

'''Амортизационный анализ''' (англ. ''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 </tex> {{---}} фактор загруженности (load factor) нашей таблицы.Пусть в нашей таблице размером <tex> m </tex> хранится <tex> n </tex> элементов, тогда <tex dpi = "150"> \alpha = \genfrac{}{}{}{}{n}{m} </tex>.Введём значение <tex>\alpha_{max}</tex>, при превышении которого таблица будет пересоздана с увеличением размера в <tex> 2 </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} \colon \Phi = 2n - \alpha_{max}m </tex>

Теперь рассмотрим все возможные случаи для Рассмотрим время работы каждой из операций <tex>\mathrm{add},\ \mathrm{remove},\ \mathrm{find}</tex>.:

#*<tex dpi = "150"> \alpha < \alpha_{max} : \alpha_i = 1 + 2 \cdot (n + 1) - \alpha_{max} m - (2n - \alpha_{max} m) = 3</tex>: потенциал увеличивается на , так как время выполнения операции <tex>2\mathrm{add} </tex>, следовательно амортизированное время {{---}} <tex>1 + 2 = 3</tex>.#*<tex dpi=150>\alpha = \alpha_{max}</tex>: таблица увеличивается в размере, так что реальная сложность {{---}} <tex> 1 + m </tex>. Но с учётом изменения потенциала амортизированная стоимость составит <tex dpia_i =150>1 + \alpha_{max}m + 2 \cdot |(\alpha_{max} \cdot m + 1 ) - \genfrac{}{}{}{}{2 \cdot \alpha_{max} \cdot m}{2}| - 2 \cdot |\alpha_{max} \cdot m - + \genfracalpha_{max}m = 3 </tex>, так как таблица увеличивается в размере, поэтому время работы операции <tex> \mathrm{add}</tex> составит <tex> 1 + \alpha_{max}{}{m </tex>, потому что сейчас в таблице <tex> n = \alpha_{max} \cdot m}{2}| = 3 </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> a_{remove} = 1 + 2 </tex>, и амортизированное время <tex> \cdot (n - 1 ) - \alpha_{max} m - (2n - 2 \alpha_{max} m) = -1 </tex>. 

Теперь рассмотрим общее время работы. <tex> t = \sum\limits_{i=1}^n a_i + \Phi_i - \Phi_{i-1}</tex>. Так как <tex>\Phi_i = 2 \cdot n - \alpha_{max} \cdot m \leqslant 2 \cdot n = O(n)</tex>.Следовательно, поэтому если <tex>a_i f(n, m) = O(1)</tex>, то данная функция удовлетворяет условию, и тогда амортизированная сложность {{---}} средняя амортизационная стоимость модифицирующих операций составит <tex>a = O(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>. == См. также ==*[[Хеш-таблица]]