3622
правки
Изменения
→Динамические хэш-таблицы
#<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}{}: n</tex> уменьшается на единицу. Возможны три два случая:
#*<tex dpi = "150">\genfrac{}{}{}{}{1}{2} \leqslant \alpha </tex>: потенциал уменьшается на 2, и амортизированное время <tex> 1 - 2 = -1 </tex>.
#*<tex dpi = "150">\alpha < \genfrac{}{}{}{}{1}{2}</tex>: потенциал увеличивается на 2, следовательно амортизированное время {{---}} <tex>1 + 2 = 3</tex>.
