65
правок
Изменения
Structure dramaticly improved
Существует реализация структуры, где все операции выполняются за амортизационную <tex>O(1)</tex>.
Список с командой порядка используется в разных алгоритмах и структурах, к примеру, в реализации полностью [[Персистентные структуры данных|персистентного дерева поиска]].
== Алгоритм за O(logn) ==
[[Файл:ListABCDwithMarks.jpg|250px|thumb|right|Пример расставления меток для списка, <tex>u=3</tex>.]]
Рассмотрим реализацию списка с командой порядка, где все операции выполняются за амортизационную <tex>O(logn\log n)</tex>. Дадим каждому элементу списка метки длины <tex>u</tex> из битов. Метки будем хранить в виде [[Сверхбыстрый цифровой бор | цифрового бора]]. Пусть <tex>u:\dfrac{n}{2}<2^u \leqslant 2n</tex>, где <tex>n</tex> {{---}} количество элементов в списке. Если после добавления или удаления элементов <tex>u</tex> перестанет удовлетворять неравенству, пересчитаем все метки заново. Пересчет меток занимает амортизационно <tex>O(1)</tex> по аналогии с саморасширяющимся массивом. Пусть метки идут по возрастанию от начала к концу списка, тогда операцию <tex>\mathrm{order(p,q)}</tex> можно сделать, сравнив метки за <tex>O(1)</tex>. Теперь опишем Опишем взаимодействие с метками при выполнении других команд.операций:
* Для <b>операция порядка:</b> <tex>\mathrm{order(p,q)}</tex> можно сделать, просто сравнив метки за <tex>O(1)</tex> (так как они идут по возрастанию);* <b>удаление вершины:</b> для выполнения <tex>\mathrm{remove(p)}</tex> просто удалим элемент <tex>p</tex> вместе с его меткойза <tex>O(1)</tex> , проверим, удовлетворяет ли <tex>u</tex> неравенству, если нет {{---}} пересчитаем. ;* Для <b>добавление вершины:</b> для <tex>\mathrm{insert(p,q)}</tex> существуют два возможных случая:** Метка <tex>r</texb>есть свободная метка: <tex>\mathrm{r.label}>\mathrm{p.label} + 1</texb>проверим, где есть ли между элементом <tex>r</tex> {{---}} следующий и следующим за <tex>p</tex> элемент в спискеним элементом свободная метка. Тогда между метками <tex>p</tex> и <tex>r</tex> Если есть свободная метка, которую мы дадим <tex>q:\mathrm{q.label} = \dfrac{\mathrm{p.label}+\mathrm{r.label}}{2}</tex>любую свободную метку между ними. После этого опять проверим <tex>u</tex> на соответствие неравенству. [[Файл:UBitTreeListABCD.jpg|350px|thumb|right|Точка {{---}} метка в листе используется.]]** <b>свободной метки нет:</b> В случае, если между метками <tex>p</tex> и <tex>q</tex> следующим за ним элементом свободной метки нет, нам придется пересчитать метки следующим образом:описанным ниже способом.
<b>Способ хранения меток.</b> Все метки хранятся в [[Сверхбыстрый цифровой бор | цифровом боре ]] высоты <tex>u</tex> (там хранятся не только используемые метки, а вообще все возможные заданной длины). В узлах будем хранить:* <b>в листьях </b> будем хранить, используется ли уже эта метка. Пусть <tex>\mathrm{weight(x)}</tex> {{---}} это количество помеченных (используемых) листьев (меток) в поддереве <tex>x</tex>, а <tex>\mathrm{size(x)}</tex> {{---}} это количество всех листьев в поддереве <tex>x</tex>;* <b>в нелистовых узлах</b> будем хранить, является ли узел переполненным. Для любой <tex>1<\alpha<2</tex> будем считать, что узел дерева переполнен, если <tex>\dfrac{\mathrm{weight(x)}}{\mathrm{size(x)}}>\dfrac{1}{\alpha^{\mathrm{height(x)}}}</tex>. Наличие переполненности мы будем хранить во всех нелистовых узлах. Стоит заметить, что все листья всегда непереполнены. В худшем случае: <tex> \dfrac{\mathrm{weight(leave)}}{\mathrm{size(leave)}} = 1 = \dfrac{1}{\alpha^{\mathrm{height(x)}}} = \dfrac{1}{\alpha^{0}}</tex>. Получается, что, чем выше, тем более разреженными должны быть поддеревья непереполненных узлов.
[[Файл:UBitTreeExample.jpg|350px|thumb|right|Пример цифрового бора для меток, где узел с крестиком {{---}} переполненный узел, а с галочкой {{---}} непереполненный для <tex>\alpha=1,5</tex>.]]
<b>Перераспределение меток.</b> Тогда, как только мы получаем команду вставить элемент, которому не хватает метки, мы поднимаемся вверх от метки элемента <tex>p</tex>, пока не найдем первый непереполненный узел. Может случиться такое, что на всем пути до корня мы не найдем ни одного непереполненного узла. Чтобы этого избежать, изменим требования к <tex>u</tex> позже. Как только мы нашли первый непереполненный узел, переназначим метки в его поддереве так, чтобы они находились друг от друга на одинаковых расстояниях (места точно хватит, так как <tex>\dfrac{\mathrm{weight(x)}}{\mathrm{size(x)}}\leqslant\dfrac{1}{\alpha^{\mathrm{height(x)}}}</tex>, если узел непереполненный). После этого плотность распределения всех занятых листьев составит примерно <tex>\dfrac{1}{\alpha^{\mathrm{height(x)}}}</tex>. * Тогда, чтобы после перераспределения меток в поддереве узла <tex>x</tex>, мы заново пришли к этому же узлу за перераспределением, нужно, чтобы его сын снова переполнился. Если <tex>y</tex> {{---}} сын <tex>x</tex>, то он переполнится, когда <tex>\dfrac{\mathrm{weight(y)}}{\mathrm{size(y)}}>\dfrac{1}{\alpha^{\mathrm{height(x) - 1}}}</tex>. Чтобы это произошло, требуется, чтобы было сделано еще <tex>\mathrm{size(y)}*(\dfrac{1}{\alpha^{\mathrm{height(x) - 1}}} - \dfrac{1}{\alpha^{\mathrm{height(x)}}}) = \mathrm{size(y)}*\dfrac{\alpha - 1}{\alpha^{\mathrm{height(x)}}}</tex> добавлений.
<b>Докажем амортизационную стоимость операции добавления.</b>* С одной стороны, повторное перераспределение меток в поддереве узла <tex>x</tex> потребуется, когда сын этого узла снова переполнится. Если <tex>y</tex> {{---}} сын <tex>x</tex>, то он переполнится, когда <tex>\dfrac{\mathrm{weight(y)}}{\mathrm{size(y)}}>\dfrac{1}{\alpha^{\mathrm{height(x) - 1}}}</tex>. Чтобы это произошло, требуется, чтобы было сделано еще <tex>\mathrm{size(y)} \cdot (\dfrac{1}{\alpha^{\mathrm{height(x) - 1}}} - \dfrac{1}{\alpha^{\mathrm{height(x)}}}) = \mathrm{size(y)} \cdot \dfrac{\alpha - 1}{\alpha^{\mathrm{height(x)}}}</tex> добавлений.* С другой стороны, следующее перераспределение переспределение меток произойдет, когда <tex>\mathrm{weight(x)} = \dfrac{\mathrm{size(x)}}{\alpha^{\mathrm{height(x)}}} = \dfrac{2\mathrm{size(y)}}{\alpha^{\mathrm{height(x)}}} </tex>. Получается, что за <tex>\dfrac{2\mathrm{size(y)}}{\alpha^{\mathrm{height(x)}}} </tex> операций перераспределения меток требуется сделать <tex>\mathrm{size(y)}*\dfrac{\alpha - 1}{\alpha^{\mathrm{height(x)}}}</tex> операций добавления.
Тогда если за каждую операцию добавления брать <tex>\dfrac{2}{\alpha-1}</tex> монет, то за добавления накопится столько монет, чтобы расплатиться за следующую операцию перераспределения в узле <tex>x</tex>. Проблема в том, что таким образом надо платить за каждый уровень, а количество уровней (бит) равно <tex>u</tex>. Тогда амортизированная стоимость добавления <tex>O(u)</tex>.
Теперь выберем такое <tex>u</tex>, чтобы корень никогда не переполнялся: <tex>\dfrac{\mathrm{weight(root)}}{\mathrm{size(root)}} < \dfrac{1}{\alpha^{\mathrm{height(root)}}} \Rightarrow \dfrac{n}{2^u} < \dfrac{1}{\alpha ^u} \Rightarrow u \geqslant \log_{\dfracfrac{ 2}{\alpha}} n</tex>. Тогда операция добавления работает за логарифмическое время от <tex>O(\log n)</tex>.
== Алгоритм за O(1) ==
[[Файл:GlobalandLocalLabelstoConst.jpg|350px|thumb|right|y-fast-tree для меток.]]
== Использование памяти ==
Из-за того, что <tex>u</tex> зависит от выбранной <tex>\alpha</tex>, <tex>\alpha</tex> сильно влияет на реализацию. Увеличивая <tex>\alpha</tex>, мы уменьшаем стоимость операции добавления (количество монет, которые надо брать: <tex>\dfrac{2}{\alpha-1}</tex>), но увеличиваем <tex>u</tex>, значит, требуется больше памяти, а, уменьшая <tex>\alpha</tex>, мы выигрываем в памяти, но проигрываем во времени операции добавления. Так как для реализации структуры мы используем <tex>\mathrm{y}{-}\mathrm{fast}{-tree}\mathrm{trie}</tex>, требуется <tex>O(n)</tex> памяти.
== Послесловие ==
* [https://en.wikipedia.org/wiki/Order-maintenance_problem Wikipedia {{---}} order maintance problem]
[[Категория:Дискретная математика и алгоритмы]][[Категория: Алгоритмы и структуры данных]]
[[Категория: Амортизационный анализ]]
[[Категория: Структуры данных]]