90
правок
Изменения
Нет описания правки
При перераспределении и копировании HAT использует мнеьше памяти, чем в стандартных подходах. Самый плохой случай для HAT - размер элементов равен размеру указателей и число элементов на один больше числа при котором происходит расширение структуры(N=ResizeValue+1). Для этого случая значени привидены в таблице:
[[Файл:Table_HAT.JPG|400px|left]]
Затраты памяти в самом плохом случае - <math>(top+leaf-1) ~= 2*sqrt(N) = O(sqrt(N))</math>. Если последний лист будет половиной полного, то ожидаемая трата памяти уменьшается до <math>(top + leaf/2) ~= 1.5*sqrt(N)</math>, а это все еще <math>O(sqrt (N))</math>.
Сравним с другими структурами, добавляющими элементы за О(1). Например отдельно связанные списки требуют O(N)памяти (один указатель для каждого элемента).
