Оценка сложности алгоритма (поиск паттернов)

[timber]

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

[Dmitriy40]

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

[timber]

Dmitriy40, спасибо!

Цитата:

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

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

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

[Dmitriy40]

timber в сообщении #1187328 писал(а):

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

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

-- 25.01.2017, 17:24 --

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

[timber]

Dmitriy40 в сообщении #1187341 писал(а):

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

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

[Dmitriy40]

timber в сообщении #1187361 писал(а):

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

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

[Pavia]

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

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