3622
правки
Изменения
Нет описания правки
Выберем какое-то k (что за k - будет видно дальше). Разобьём их на s блоков размером от k/2 до 2k, а точнее
B_{11} < B_{12} < ... < B_{1n1} < B_{21} < B_{22} < ... < B_{2n2} < ... < B_{s1} < B_{s2} < ... < B_{sns}
Выберем в каждом блоке какого-нибудь представителя. И поместим этих представителей в x-fast-trie. Всего в x-fast-trie будет O(2 * n * w / k) элементов. Поэтому если выбрать k = \thetaOmega(w), то x-fast-trie будет занимать O(n) памяти.
Каждый лист x-fast-trie является представителем блока, а все остальные элементы блока (в т. ч. и представителя) подвесим к листу как сбалансированное двоичное дерево поиска. В дереве может храниться от w/2 До 2 * w элементов, поэтому его высота - O(log w).
===Ассимптотика===
Заметим, что вставка, которая не модифицирует верхний бор, выполняется за истинный log(w), также и succ, pred.
Плохие операции — которые модифицируют верхний бор. Но они не происходят слишком часто. // O - сверху, Omega - снизу, Theta - и сверху и снизу - памятка для тебя, чтобы не запутатьсяПрименим амортизационный анализ, используя метод предоплаты. Копим деньги на дешевых операциях. Слиянием массивов осуществляется за O(w), так как после каждой операции слияния/разделения деревья оказываются на расстоянии Thetaи разделение. Поэтому, если мы накопим Omega(w) от границдополнительных денег на дешёвых операциях, то сумеем расплатиться за все остальные, просто кладя константное число дополнительных монет во время каждой операции. Худший случай — для разделения, если мы дальше будем только добавлять элементы - было: w/2 - 1 и 2*w, - слили, стало: 5w/4 и 5wбольше 2 * w, разделели, таким образом получили два дерева с 5/4* w элементами. В нижнее дерево должно произойти порядка w вставок и удаленийХудший случай для слияния, чтобы оно с чем-то слилось или разделилось.Применим амортизационный анализ. Копим деньги на дешевых операциях: когда добавляем вершину, то кладём 4/3 монетки. Таким образом мы успеем накопить на разделение при превышении размера в у нас w элементов (просиходит после разделения 2 * w+ 1 дерева). При удалении кладём ещё 2 монеткиЗаметил, что в каждом случае дерево находится на расстоянии Theta(w) от границ. И таким образом Следовательно, если мы будем класть определённое константное число монет, то скопим их достаточно, чтобы расплатиться за преобразование верхнего дерева. Получаем амортизированную оценку O(log(w)) и истинную - O(w).
Здесь не имеет смысла использовать сливаемые деревья поиска, так как после слияния/разделения все равно нужно модифицировать верхний бор.
Получилась та же оценка на операции, что и у Ван Эмде Боаса, но структура данных занимает O(n) памяти.
