В чем сложность регулярного выражения?

Ответ 1

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

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

Ответ 2

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

Ответ 3

Если вы используете обычный (TCS: no backreference, concatenation, alternation, Kleene star) regexp и regexp уже скомпилирован, тогда он O (n).

Ответ 4

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

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