90
правок
Изменения
Нет описания правки
[[Файл: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)памяти (один указатель для каждого элемента).
