Изменения

Перейти к: навигация, поиск

Амортизационный анализ

3565 байт убрано, 19:18, 4 сентября 2022
м
rollbackEdits.php mass rollback
==Основные определения==
{{Определение | definition =
'''Амортизационный анализ''' (англ. ''amortized analysis'') {{---}} метод подсчета подсчёта времени, требуемого для выполнения последовательности операций над структурой данных. При этом время усредняется по всем выполняемым операциям, и анализируется средняя производительность операций в худшем случае.
}}
Такой анализ чаще всего используется, чтобы показать, что даже если некоторые из операций последовательности являются дорогостоящими, то при усреднении по всем операциям средняя их стоимость будет небольшой за счёт низкой частоты встречаемости. Подчеркнём, что оценка, даваемая амортизационным анализом, не является вероятностной: это оценка среднего времени выполнения операций для худшего случая.
}}
Амортизационный анализ использует следующие методы:
 1. #Метод усреднения (метод группового анализа). 2. #Метод потенциалов. 3. #Метод предоплаты (метод бухгалтерского учетаучёта).
==Метод усреднения==
=====Стек с multipop=====
Рассмотрим [[Стек | стек ]] с операцией <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>.
Распишем приведённые рассуждения более формально.
О методе потенциалов
|statement =
Введём для каждого состояния структуры данных величину <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>
|proof =
<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>a_{pop} = 1 - 1 = 0,</tex> так как время выполнения операции <tex>\mathrm{pop}{}</tex> {{---}} <tex>1</tex>, а изменение потенциала {{---}} <tex>-1</tex>.
#* <tex>a_{multipop} = k - k = 0,</tex> так как время выполнения операции <tex>\mathrm{multipop}{(k)}</tex> {{---}} <tex>k</tex>, а изменение потенциала {{---}} <tex>-k</tex>.
# Для любого <tex>i: \enskip \Phi_i = O(n),</tex> так как элементов в стеке не может быть больше <tex>n</tex>
Таким образом, <tex>f(n, m) = 1</tex>, а значит, средняя амортизационная стоимость операций <tex>a = O(1)</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>\mathrm{add}{}</tex>: <tex>\, n</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>\mathrm{push}{}</tex> будем использовать две монеты {{---}} одну для самой операции, а вторую {{---}} в качестве резерва. Тогда для операций <tex>\mathrm{pop}{}</tex> и <tex>\mathrm{multipop}{}</tex> учётную стоимость можно принять равной нулю и использовать для удаления элемента монету, оставшуюся после операции <tex>\mathrm{push}{}</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>. == См. также ==*[[Хеш-таблица]]
==Источники информации==
* [[wikipedia:Amortized_analysis | Wikipedia {{---}} Amortized analysis]]
* Томас Кормен. Алгоритмы. Построение и анализ. - Санкт-Петербург, 2005. стр. 483-491.
* [[wikipedia:Amortized_analysis | Wikipedia {{---}} Amortized analysis]]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Амортизационный анализ]]
1632
правки

Навигация