73
правки
Изменения
Добавлен раздел "Сложность алгоритма"
Как пишет Д. Кнут короткого доказательства алгоритма не известно, и вероятно оно ни когда не будет найдено. Для доказательства своего алгоритма Ху и Таккеру потребовалось 3 теоремы и 2 леммы.
== Сложность алгоритма ==
Для реализации данного алгоритма потребуется <tex>O(n)</tex> памяти и <tex>O(n log n)</tex> времени на построение дерева.
Разберем оценку. Для доказательства такой оценки времени введем понятие ''локально минимальной совместимой пары'' (л.м.с.п), пара <tex>(w_{l},w_{r})</tex> является л.м.с.п, когда выполнены следующие условия <tex>w_{r}<w_{i}</tex> для всех вершин <tex>i</tex> совместимых с <tex>l</tex> и <tex>w_{l} \le w_{j}</tex> для всех вершин <tex>j</tex> совместимых с <tex>r</tex>. Так же докажем следующую лемму.
{{Лемма
|id=lemma1
|about=1
|statement=
Пусть <tex>a</tex> — любая вершина в последовательности, состоящей из вершин алфавита и вершин образованных в результате комбинации, <tex>w_{i}</tex> — вес наименьшего узла <tex>i</tex>, совместимого с <tex>a</tex>. Если в результате комбинирования некоторой л.м.с.п. какой-нибудь новый узел <tex>d</tex> становится совместимым c <tex>a</tex>, то <tex>w_{i}<w_{d}</tex> В частности, л.м.с.п. в последовательности узлов будет оставаться л.м.с.п., пока комбинируются другие л.м.с.п.
Из этой леммы следует, что дерево, получаемое комбинированием л.м.с.п., не зависит от того, в каком порядке они комбинируются.
|proof=
Рассмотрим произвольный узел <tex>a</tex> и предположим, что вес наименьшего узла, совместимого с <tex>a</tex>, равен <tex>w_{i}</tex>.
Пусть комбинируется л.м.с.п. <tex>(b, c)</tex>, причем <tex>a</tex> ближе к <tex>b</tex>. Тогда между <tex>a</tex> и <tex>b</tex> нет вершин алфавита и хотя бы одна из <tex>b</tex>, <tex>c</tex> должна быть вершиной алфавита, иначе при слиянии <tex>(b, c)</tex> не появилось бы новых вершин (кроме <tex>bc</tex>), совместимых с <tex>a</tex>.
Заметим, что <tex>w_{i}</tex> может находиться в любой стороне от <tex>a</tex>. Если вершина <tex>w_{i}</tex> лежит справа от <tex>a</tex>, то она не вершина алфавита. Пусть <tex>d</tex> — вершина, которая становится совместимой с <tex>a</tex> после слияния <tex>(b, c)</tex> (она может быть как алфавитной так и слитой). Тогда <tex>d</tex> должна быть совместима с <tex>c</tex> в исходной последовательности и в силу локальной минимальности пары <tex>(b, c)</tex> имеем <tex>w_{b} \le w_{d}</tex>.
Но <tex>w_{i}<w_{b}</tex>, так как <tex>b</tex> совместим с <tex>a</tex> в исходной последовательности, а <tex>w_{i}</tex> является наименьшим совместимым с <tex>a</tex> весом. Поэтому <tex>w_{i} \le w_{b} \le w_{d}</tex>.
Мы доказали, что вес наименьшего узла, совместимого с любым узлом, не может уменьшиться. Отсюда следует, что любая л.м.с.п. <tex>(x, y)</tex> останется л.м.с.п. после слияния другой л.м.с.п., потому что <tex>x</tex> останется наименьшим узлом, совместимым с <tex>y</tex>, и наоборот.
}}
Теперь согласно этой лемме нам не придется искать минимально совместимую пару, что весьма долго, достаточно лишь находить л.м.с.п. при этом не важно в каком порядке комбинировать л.м.с.п. По этому нам необходимо иметь массив размера <tex>n</tex> из которого мы будем удалять л.м.с.п и создавать новую вершину, на нем легко будет осуществлять поиск л.м.с.п. А так же необходим массив размера <tex>2n</tex> хранящий дерево, для реализации следующего шага. Второй шаг легко осуществить имея сохраненное дерево, проходом по дереву. Третий шаг реализованный стековым алгоритмом работает за <tex>2n</tex> времени и необходимо <tex>4n</tex> памяти, <tex>n</tex> на стек, <tex>n</tex> на хранения уровней вершин и <tex>2n</tex> на хранение итогового дерева. Итак общая оценка как раз получается <tex>O(n)</tex> памяти и <tex>O(n log n)</tex> времени.
== Литература ==
* Т.Ч.Ху и М.Т.Шинг Комбинаторные алгоритмы — стр. 166 — ISBN 5-85746-761-6
* Дональд Кнут Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е изд. — М.: «Вильямс», 2007. — 824 с. — ISBN 5-8459-0082-4
