2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Оценка сложности алгоритма (поиск паттернов)
Сообщение25.01.2017, 16:09 


14/12/14
454
SPb
Подскажите пожалуйста, есть ли универсальная формула и какая, позволяющая приблизительно оценить вычислительную сложность алгоритма распознавания паттернов на алфавите длиной $n$ символов?
Ну например, у нас есть алфавит из трех $n=3$ букв: ${a, b, c}$. И есть длинная случайная последовательность символов данного алфавита, допустим: $aabbcbaaabbbcaccb ... cbbaacbbbccabc$. Нужно быстро понять за сколько примерно итераций машина обнаружит какой-то определенный паттерн, например: $(abbc)$?
Может есть какая-то общая комбинаторная формула?

 Профиль  
                  
 
 Re: Оценка сложности алгоритма (поиск паттернов)
Сообщение25.01.2017, 16:31 
Заслуженный участник


20/08/14
11058
Россия, Москва
Есть варианты алгоритмов с линейным (от длины строки) временем, даже в вики. Вам подойдёт "Автоматный алгоритм Алгоритм Ахо-Корасик" или "Алгоритм Кнута-Морриса-Пратта" с точно линейным временем даже в худшем случае. Описания, оценки и формулы доступны там же в вики.

 Профиль  
                  
 
 Re: Оценка сложности алгоритма (поиск паттернов)
Сообщение25.01.2017, 16:40 


14/12/14
454
SPb
Dmitriy40, спасибо!

Цитата:
Время работы зависит от организации данных. Например:

Если таблицу переходов автомата хранить как индексный массив — расход памяти $O(n\sigma)$, вычислительная сложность $O(n\sigma + H + k)$, где $H$ — длина текста, в котором ищем, $n$ — общая длина всех слов в словаре, $\sigma$ — размер алфавита, $k$ — общая длина всех совпадений.


Как определяется $k$ -- общая длина всех совпадений?

 Профиль  
                  
 
 Re: Оценка сложности алгоритма (поиск паттернов)
Сообщение25.01.2017, 17:19 
Заслуженный участник


20/08/14
11058
Россия, Москва
timber в сообщении #1187328 писал(а):
Как определяется $k$ -- общая длина всех совпадений?

Это нужно в случае поиска всех вхождений паттерна в тексте. И считается как количество всех возможных вхождений паттерна умноженное на длину паттерна. Для поиска лишь первого вхождения можно принять равным длине паттерна.

-- 25.01.2017, 17:24 --

Ну и мне кажется алгоритм Кнута-Морриса-Пратта попроще, да и оценка его времени проще.

 Профиль  
                  
 
 Re: Оценка сложности алгоритма (поиск паттернов)
Сообщение25.01.2017, 17:58 


14/12/14
454
SPb
Dmitriy40 в сообщении #1187341 писал(а):
Ну и мне кажется алгоритм Кнута-Морриса-Пратта попроще, да и оценка его времени проще.

Правильно понимаю, что в случае использования алгоритма Кнута-Морриса-Пратта оценка будет: $\leqslant 2H$, где $H$ -- длина текста в котором ищем паттерн?

 Профиль  
                  
 
 Re: Оценка сложности алгоритма (поиск паттернов)
Сообщение25.01.2017, 18:35 
Заслуженный участник


20/08/14
11058
Россия, Москва
timber в сообщении #1187361 писал(а):
Правильно понимаю, что в случае использования алгоритма Кнута-Морриса-Пратта оценка будет: $\leqslant 2H$, где $H$ -- длина текста в котором ищем паттерн?

Ну в таблице написано так, но на странице описания самого алгоритма приведена как мне кажется более вменяемая оценка $O(H+m)$ ($m$ - длина паттерна). Конечно $O(H+m) \leqslant O(2H)$ так что можно и $2H$ оставить, всё равно же линейно.

 Профиль  
                  
 
 Re: Оценка сложности алгоритма (поиск паттернов)
Сообщение25.01.2017, 19:39 
Аватара пользователя


31/10/08
1244
timber
ДКА $O(H)$ в среднем $T(H/2)$.

Dmitriy40
Не вводите народ в заблуждение. У символа $O()$ - есть конкретный смысл, который вы нарушаете. И оттого делаете неправильные выкладки.
Читайте учитесь:
https://ru.wikipedia.org/wiki/«O»_большое_и_«o»_малое

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group