и используя такой же объем
опять за
O(mk), и используя такой же объем памяти. Длина слова де Бройна равна
mk+k-1, т.е. тоже
O(mk), следовательно, такой алгоритм оптимален по порядку. Можно улучшить «внутренние» показатели эффективности такого алгоритма, т.е. уменьшить объем памяти, занимаемый внутренними структурами данных и время их обработки, не учитывая внешнюю память и время, используемые для вывода результата. Различные алгоритмы для порождения слов де Бройна довольно часто упоминаются в литературе, в том числе и алгоритмы с лучшими показателями «внутренней» эффективности. Часть из них основана на неожиданной связи между словами де Бройна и словами Линдона (Lyndon words).
Слово Линдона длины
k в алфавите мощности
m — это лексикографически минимальный представитель
m-цикла, т.е. класса эквивалентности
m-слов по циклическим перестановкам их символов. Оказывается, что верно следующее утверждение.
Утверждение 4. [11] Конкатенация лексикографически упорядоченной последовательности всех слов Линдона длин, делящих
k, в некотором алфавите дает лексикографически минимальный цикл де Бройна шага
k в том же алфавите (для получения из него слова де Бройна достаточно добавить первые
k-1 символов из начала в конец). Эффективный (требующий ограниченного константой «внутреннего» времени на построение одного слова Линдона) алгоритм построения слов Линдона и слов де Бройна на их основе представлен в [20]. Другие алгоритмы можно найти в [21–28]. В работе [29] эмпирически сравнивается эффективность по времени алгоритмов из [20], [25] и [27], и последний демонстрирует наиболее высокое быстродействие.
Содержание Назад Вперед
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий