21
правка
Изменения
Нет описания правки
Введём такую потенциальную функцию, что она будет "запасать" время по мере удаления фактора загруженности от <tex dpi = "130">\genfrac{}{}{}{}{1}{2}</tex>:
<tex> \Phi = 2|{n - m/2}| </tex>
Предположим, не умаляя общности, что<tex>\alpha_{max} = 1</tex>.
Теперь рассмотрим все возможные случаи для каждой из операций <tex>add, remove, find</tex>.
#Операция <tex>\mathrm{add}{}: n</tex> увеличивается на единицу. Следовательно, имеются три случая:
##<tex dpi = "130">\alpha < \genfrac{}{}{}{}{1}{2}</tex>: потенциал уменьшается на 2, и амортизированное время <tex> 1 - 2 = -1 </tex>.
##<tex>\alpha = 1</tex>: Таблица увеличивается в размере, так что реальная сложность {{---}} <tex> 1 + m </tex>. Но потенциал изменяется с <tex>m</tex> до нуля, следовательно амортизационная сложность {{---}} <tex> 1 + m - m = 1</tex>.
#<tex>\mathrm{find}{}:</tex> Потенциал Рассмотрим два случая:## Элементы распределяются по таблице достаточно равномерно: время поиска элемента в списке {{---}} <tex>O(1)</tex>, потенциал не изменяется, следовательно и реальная, и амортизированная сложности {{---}} <tex>1</tex>.## В случае, если все элементы оказываются размещены в одном списке, время поиска элемента достигает <tex>O(n)</tex>. Это время может быть улучшено до <tex>O(log n)</tex>, если вместо списков использовать сбалансированные деревья поиска.
#<tex>\mathrm{remove}{}: n</tex> уменьшается на единицу. Возможны три случая:
##<tex dpi = "130">\genfrac{}{}{}{}{1}{2} \leqslant \alpha < 1 </tex>: потенциал уменьшается на 2, и амортизированное время <tex> 1 - 2 = -1 </tex>.
##<tex>\alpha = 1</tex>: Таблица уменьшается в размере, следовательно реальная сложность {{---}} <tex dpi = "130"> 1 + \genfrac{}{}{}{}{m}{4}</tex>, а потенциал меняется от <tex dpi = "130">\genfrac{}{}{}{}{m}{2}</tex> до нуля, следовательно амортизированная стоимость {{---}} <tex dpi = "130"> 1 + \genfrac{}{}{}{}{m}{4} - \genfrac{}{}{}{}{m}{2} = 1 - \genfrac{}{}{}{}{m}{4}</tex>.
В каждом случае амортизированное время одной операции в среднем случае {{---}} <tex>O(1)</tex>, в худшем случае {{---}} <tex>O(n)</tex>. Если мы создадим нашу таблицу так, что <tex dpi = "130">\alpha = \genfrac{}{}{}{}{1}{2}</tex>, то изначально потенциал будет равен нулю. И так мы будем знать, что потенциал никогда не станет меньше этого значения; в итоге амортизированная стоимость будет верхней границей реальной оценки. Следовательно, сложность последовательности из <tex> n</tex> операций в среднем случае будет равна <tex>O(n)</tex>.
==Метод предоплаты==
