Не могу понять как можно дать оценку сложности алгоритму поиска последовательности де Брейна $%B(n,k)$%. Тут $%n$% - это количество символов в алфавите, а $%k$% - длина слов. Мне известно два способа поиска последовательности.

Способ 1 (через Гамильтонов цикл):

  1. Взять орграф на $%n^{k}$% вершинах. Вершинами будут являться всевозможные $%k$%-меры. В качестве ребер будут строки длины $%k-1$%. Две вершины соединять направленным ребром только если суффикс исходной вершины совпадает с префиксом конечной вершины.
  2. Найти Гамильтонов цикл. Он задает порядок перехода от одного $%k$%-мера к другому. Обход по этому циклу, который проходит по всем вершинам восстановит мне циклическое слово.

Способ 2 (через Эйлеров цикл):

  1. Взять $%k$%-меры в качестве ребер. А в качестве вершин взять $%k-1$%-меры.
  2. Построить Эйлеров цикл, т.е. обойти все ребра в графе ровно по одному разу.

На словах понятно в общем, но как дать этому описанию формальную оценку через $%O$% большое? Можно ли например приравнять сложность алгоритма поиска последовательности де Брейна к сложности построения Эйлерова цикла? Или надо еще как-то учитывать, то что сначала надо построить граф?

задан 27 Мар '16 15:04

изменен 27 Мар '16 18:38

В таких случаях нужно давать определения или ссылки.

(27 Мар '16 15:50) falcao

@falcao, обновил вопрос. Может подскажите что-нибудь?

(27 Мар '16 18:35) gus

@gus: задача нахождения гамильтоновых циклов в общем случае очень сложна, а для эйлеровых графов есть простой и быстрый алгоритм Флёри. Им и надо, наверное, воспользоваться.

(27 Мар '16 20:27) falcao
10|600 символов нужно символов осталось
1

Думаю (n^(k-1))^2 т.к. количество вершие графа деБрайна n^(k-1) и для построения направленного эйлерова графа нужно для каждой вершины просмотреть все включая саму себя. Ну потом ещё пройтись по всем рёбрам, а это уже O(n^(k-1)) поэтому эту чать вычислений можно не учитывать.

ссылка

отвечен 27 Мар '16 23:51

изменен 27 Мар '16 23:52

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,066
×395
×169
×135
×45

задан
27 Мар '16 15:04

показан
581 раз

обновлен
27 Мар '16 23:52

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru