3622
правки
Изменения
→Динамические хэш-таблицы
Предположим, не умаляя общности, что <tex>\alpha_{max} = 1</tex>.
Теперь рассмотрим все возможные случаи для каждой из операций <tex>\mathrm{add},\ \mathrm{remove},\ \mathrm{find}</tex>.
#<tex>\mathrm{add}{}</tex>: <tex>\, n</tex> увеличивается на единицу. Следовательно, имеются возникают три случая:
#*<tex dpi = "150">\genfrac{}{}{}{}{1}{2} \leqslant \alpha < 1 </tex>: потенциал увеличивается на <tex>2</tex>, следовательно амортизированное время {{---}} <tex>1 + 2 = 3</tex>.
#*<tex dpi = "150">\alpha < \genfrac{}{}{}{}{1}{2}</tex>: потенциал уменьшается на <tex>2</tex>, и амортизированное время <tex> 1 - 2 = -1 </tex>.
