Изменения

Перейти к: навигация, поиск

Обсуждение участника:SergeyBud

242 байта добавлено, 11:57, 12 июня 2014
Расход памяти
===Расход памяти===
При перераспределении и копировании HAT использует меньше дополнительной памяти, чем в стандартных подходахк расширению массивов, то есть полном перекопировании и перераспределении всего массива. Самый плохой случай для HAT {{---}} размер элементов равен размеру указателей, и число элементов на один больше числа, при котором происходит расширение структуры(<tex>N=ResizeValue+1</tex>).Затраты доролнительной дополнительной памяти (уже выделенной, но еще не используемой) в самом плохом случае {{---}} <math>(top+leaf-1) ~= 2\sqrt{N} = O(\sqrt{N})</math>(этот случай при пустой HAT {{---}} в <tex>top</tex> один указатель на единственный пустой лист). Если последний лист в листе будет половиной полного<tex>power/2</tex> элементов, то ожидаемая трата дополнительной памяти уменьшается до <math>(top + leaf/2) \approx 1.5\sqrt{N}</math> (top {{---}} главный массив, leaf {{---}} листья), а это все еще <math>O(\sqrt{N})</math>.
Сравним с другими структурами, добавляющими элементы за <math>O(1)</math>. Например, отдельно связанные списки требуют O(N) дополнительной памяти (один указатель для каждого элемента).
90
правок

Навигация