Какова сложность регулярного выражения?

Question

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

Answer 1

Ответ зависит от того, что именно вы подразумеваете под «регулярными выражениями».Классические регулярные выражения могут быть скомпилированы в Детерминированные конечные автоматы , которые могут соответствовать строке длины N за O(N) времени.Некоторые расширения языка регулярных выражений меняют это к худшему.

Вы можете найти следующий интересующий документ: Соответствие регулярному выражению может быть простым и быстрым .

Answer 2

неограниченно - вы можете создать регулярное выражение, которое никогда не заканчивается, в пустой строке ввода.

Answer 3

Если вы используете обычный (TCS: без обратной ссылки, конкатенации, чередования, звезды Клини) регулярное выражение и регулярное выражение уже скомпилировано, то это O (n).

Answer 4

Если вы ищете точные асимптотические границы для RegEx (без учета самого выражения), то их нет. Как указывает Алекс, вы можете создать регулярное выражение O (1) или регулярное выражение Omega (бесконечность). Будучи чисто математическим алгоритмом, механизм регулярных выражений был бы слишком сложным для выполнения какого-либо формального асимптотического анализа (за исключением того факта, что такой анализ в основном бесполезен).

Скорость роста определенного выражения (поскольку это, в любом случае, представляет собой алгоритм) была бы гораздо более значимой, хотя не обязательно легче анализировать.