21
правка
Изменения
Динамические хэш-таблицы
Стоит отметить, что изменение размера массива всегда должно быть геометрическим (в <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">\genfrac{}{}{}{}alpha < \alpha_{1}{2max} \leqslant \alpha < 1 </tex>: потенциал увеличивается на <tex>2</tex>, следовательно амортизированное время {{---}} <tex>1 + 2 = 3</tex>.#*<tex dpi = "150">\alpha < = \genfrac{}{}{}{}alpha_{1max}{2}</tex>: потенциал уменьшается на <tex>2</tex>, и амортизированное время <tex> 1 - 2 = -1 </tex>.#*<tex dpi=150>\alpha = 1</tex>: таблица увеличивается в размере, так что реальная сложность {{---}} <tex> 1 + m </tex>. Но с учётом изменения потенциала амортизированная стоимость составит <tex dpi=150>1 + m + 2 \cdot |m + 1 - \genfrac{}{}{}{}{2 \cdot m}{2}| - 2 \cdot |m - \genfrac{}{}{}{}{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 dpi = "150">\genfrac{}{}{}{}{1}{2} \leqslant \alpha </tex>: потенциал Потенциал уменьшается на <tex> 2 </tex>, и амортизированное время <tex> 1 - 2 = -1 </tex>.#*<tex dpi = "150">\alpha < \genfrac{}{}{}{}{1}{2}</tex>: потенциал увеличивается на <tex>2</tex>, следовательно амортизированное время {{---}} <tex>1 + 2 = 3</tex>.
