3622
правки
Изменения
→Динамические хэш-таблицы: расписан потенциал хэш-таблицы
Стоит отметить, что изменение размера массива всегда должно быть геометрическим (в <tex> k </tex> раз), потому как при изменении размера на константу нам потребуется <tex>O(n)</tex> раз пересоздать таблицу, что приведёт к сложности операции <tex>\mathrm{add}{}</tex> в <tex> O(n^2) </tex>.
Введём такую потенциальную функцию, что она будет "запасать" время по мере удаления фактора загруженности от <tex dpi = "150">\genfrac{}{}{}{}{1}{2}</tex>:<tex> \colon \Phi = 2|{n - \genfrac{}{}{}{}{m/}{2}}| </tex>
Предположим, не умаляя общности, что <tex>\alpha_{max} = 1</tex>.
Теперь рассмотрим все возможные случаи для каждой из операций <tex>\mathrm{add},\ \mathrm{remove},\ \mathrm{find}</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>.
#*<texdpi=150>\alpha = 1</tex>: Таблица таблица увеличивается в размере, так что реальная сложность {{---}} <tex> 1 + m </tex>. Но потенциал изменяется с учётом изменения потенциала амортизированная стоимость составит <texdpi=150>1 + m</tex> до нуля, следовательно амортизационная сложность + 2 \cdot |m + 1 - \genfrac{}{}{}{}{2 \cdot m}{2}| -2 \cdot |m --\genfrac{}{}{}{} <tex> 1 + m - {m }{2}| = 13 </tex>.
#<tex>\mathrm{find}{}</tex>: Рассмотрим два случая:
#* Элементы распределяются по таблице достаточно равномерно: время поиска элемента в списке {{---}} <tex>O(1)</tex>, потенциал не изменяется, следовательно и реальная, и амортизированная сложности {{---}} <tex>1</tex>.
