Изменения

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

Сверхбыстрый цифровой бор

6 байт добавлено, 01:20, 9 июня 2013
Сверхбыстрый цифровой бор (y-fast-trie)
Выберем в каждом блоке какого-нибудь представителя. И поместим этих представителей в <tex>x-fast-trie</tex>. Всего в <tex>x-fast-trie</tex> будет <tex>O(\frac{2 \cdot n \cdot w} {k})</tex> элементов. Поэтому если выбрать <tex>k = \Omega(w)</tex>, то <tex>x-fast-trie</tex> будет занимать <tex>O(n)</tex> памяти.
Каждый лист <tex>x-fast-trie</tex> является представителем блока, а все остальные элементы блока (в т. ч. и представителя) подвесим к листу как сбалансированное двоичное дерево поиска. В дереве может храниться от <tex>\frac{w}{2} </tex> До <tex>2w</tex> элементов, поэтому его высота - <tex>O(\log w)</tex>.
Все деревья поиска занимают <tex>O(n)</tex> памяти, и <tex>x-fast-trie – O(n)</tex> памяти. Поэтому <tex>y-fast-trie</tex> тоже занимает <tex>O(n)</tex> памяти.
Анонимный участник

Навигация