90
правок
Изменения
Нет описания правки
Затраты памяти в самом плохом случае - <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) памяти (один указатель для каждого элемента).
===Эффективность===
Сравнивая со стандартным массивом переменной длины, реализованным в стандартной библиотеке С++, мы получаем, что благодаря предвычислению (1<<power)-1, разыменование элементов в HAT происходит приблизительно в два раза быстрее, чем разыменование в стандартном массиве С++. Рассотрим несколько граффиков, показывающих скорость работы HAT на некоторых алгоритмах:
1) Быстрая сортировка(QuickSort). Граффик сравнивает HAT и стандартный массив в С++.
