13
правок
Изменения
м
Поправка пунктуации. ("следовательно" здесь - вводное слово, а не союз)
#*<tex>\alpha = \alpha_{max} : a_i = 1 + \alpha_{max}m + 2 \cdot (\alpha_{max} m + 1) - 2\alpha_{max} m - 2 \alpha_{max} m + \alpha_{max} m = 3 </tex>, так как таблица увеличивается в размере, поэтому время работы операции <tex> \mathrm{add} </tex> составит <tex> 1 + \alpha_{max}m </tex>, потому что сейчас в таблице <tex> n = \alpha_{max} m </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> уменьшается на единицу. Тогда амортизационное время работы с учётом изменения потенциала составит:
