Изменения

Рассмотрим [[Хеш-таблица | хэш-таблицы]], использующие цепочки в виде [[Список | списков]] для [[Разрешение коллизий | разрешения коллизий]]. Для того, чтобы поиск элемента в цепочке не начал слишком сильно влиять на производительность, введём величину <tex> \alpha </tex> {{---}} фактор загруженности (load factor) нашей таблицы.Пусть в нашей таблице размером <tex> m </tex> хранится <tex> n </tex> элементов, тогда <tex dpi = "150"> \alpha = \genfrac{}{}{}{}{n}{m} </tex>.Введём значение <tex>\alpha_{max}</tex>, при превышении которого таблица будет пересоздана с увеличением размера в <tex> 2 </tex> раза, и все элементы будут перераспределены по-новому (rehashing).Из-за этого сложность операции <tex>\mathrm{add}{}</tex> из <tex> O(1) </tex> станет в худшем случае составит <tex> O(n) </tex>, так как для пересоздания таблицы нам требуется <tex> O(n) </tex> операций.Стоит отметить, что изменение размера массива всегда должно быть геометрическим (в <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 dpi = "150"> \alpha < \alpha_{max} : \alpha_i = 1 + 2 \cdot (n + 1) - \alpha_{max} m + 2n - \alpha_{max} m = 3</tex>: потенциал увеличивается на , так как время выполнения операции <tex>2\mathrm{add} </tex>, следовательно амортизированное время {{---}} <tex>1 + 2 = 3</tex>.#*<tex dpi=150>\alpha = \alpha_{max}</tex>: таблица увеличивается в размере, так что реальная сложность {{---}} <tex> 1 + m </tex>. Но с учётом изменения потенциала амортизированная стоимость составит <tex dpia_i =150>1 + \alpha_{max}m + 2 \cdot |(\alpha_{max} \cdot m + 1 ) - \genfrac{}{}{}{}{2 \cdot \alpha_{max} \cdot m}{2}| - 2 \cdot |\alpha_{max} \cdot m - + \genfracalpha_{max}m = 3 </tex>, так как таблица увеличивается в размере, поэтому время работы операции <tex> \mathrm{add}</tex> составит <tex> 1 + \alpha_{max}{}{m </tex>, потому что сейчас в таблице <tex> n = \alpha_{max} \cdot 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> a_{remove} = 1 + 2 </tex>, и амортизированное время <tex> \cdot (n - 1 ) - 2 \alpha_{max} m + 2n - \alpha_{max} m = -1 </tex>.

 Теперь рассмотрим общее время работы. <tex> t = \sum\limits_{i=1}^n a_i + \Phi_i - \Phi_{i-1}</tex>. Так как <tex>\Phi_i = 2 \cdot n - \alpha_{max} \cdot m \leqslant 2 \cdot n = O(n)</tex>.Следовательно, поэтому если <tex>a_i f(n, m) = O(1)</tex>, то данная функция удовлетворяет условию, и тогда амортизированная сложность {{---}} средняя амортизационная стоимость модифицирующих операций составит <tex>a = O(1)</tex>.