Изменения

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

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

601 байт убрано, 22:19, 13 мая 2014
Нет описания правки
Теперь рассмотрим все возможные случаи для каждой из операций <tex>\mathrm{add},\ \mathrm{remove},\ \mathrm{find}</tex>.
#<tex>\mathrm{add}{}</tex>: <tex>\, n</tex> увеличивается на единицу. Следовательно, возникают три два случая:#*<tex dpi = "150"> \alpha < \alpha_{max} </tex>: потенциал увеличивается на <tex>(2 \cdot (n + 1) - \alpha_{max} \cdot m) - (2 \cdot n - \alpha_{max} \cdot m) = 2</tex>, следовательно амортизированное время {{---}} <tex>1 + 2 = 3</tex>.
#*<tex dpi=150>\alpha = \alpha_{max}</tex>: таблица увеличивается в размере, так что реальная сложность {{---}} <tex> 1 + m </tex>. Но с учётом изменения потенциала амортизированная стоимость составит <tex dpi=150>1 + m + 2 \cdot |\alpha_{max} \cdot m + 1 - \genfrac{}{}{}{}{2 \cdot \alpha_{max} \cdot m}{2}| - 2 \cdot |\alpha_{max} \cdot m - \genfrac{}{}{}{}{\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> -((2 \cdot n - \alpha_{max} \cdot m) - (2 \cdot (n + 1) - \alpha_{max} \cdot m)) = 2 </tex>, и амортизированное время <tex> 1 - 2 = -1 </tex>.
В каждом случае амортизированное Теперь рассмотрим общее время одной операции в среднем случае {{---}} работы. <tex>O(t = \sum\limits_{i=1)</tex>, в худшем случае {}^n a_i + \Phi_i - \Phi_{i---}1} <tex>O(n)</tex>. Если мы создадим нашу таблицу так, что Так как <tex dpi = "150">\alpha Phi_i = 2 \cdot n - \genfrac{}{}{}{}{alpha_{max}}{\cdot m \leqslant 2}\cdot n = O(n)</tex>, то изначально потенциал будет равен нулю. И так мы будем знать, что потенциал никогда не станет меньше этого значения; в итоге амортизированная стоимость будет верхней границей реальной оценки. Следовательно, сложность последовательности из если <tex>na_i = O(1)</tex> операций в среднем случае будет равна , то данная функция удовлетворяет условию, и тогда амортизированная сложность {{---}} <tex>O(n1)</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 = \genfrac{}{}{}{}{\sum\limits^{n}_{i = 1} {t_i}}{n} = \genfrac{}{}{}{}{n \cdot O(f(n, m))}{n}</tex> <tex>= O(f(n, m))</tex>.
====Примеры====
21
правка

Навигация