50
Какова сложность в отношении длины строки, которая требуется для сравнения регулярных выражений в строке?Какова сложность регулярного выражения?
A
ответ
41
Ответ зависит от того, что именно вы подразумеваете под «регулярными выражениями». Классические regexes могут быть compiled в Deterministic Finite Automata, которые могут соответствовать строке длины N в O(N) времени. Некоторые расширения языка регекса меняются, что еще хуже.
Возможно, вы найдете следующий документ: Regular Expression Matching Can Be Simple And Fast.
7
unbounded - вы можете создать регулярное выражение, которое никогда не заканчивается, на пустой строке ввода.
+0
Просто из любопытства, не могли бы вы привести пример Алекса? – 2010-12-07 15:50:26
5
Если вы используете обычный (TCS: без обратной ссылки, конкатенации, чередования, звезды Kleene) regexp и regexp уже скомпилированы, то это O (n).
1
Если вы ищете жесткие асимптотические оценки на RegEx (без учета самого выражения), то их нет. Как указывает Алекс, вы можете создать регулярное выражение O (1) или регулярное выражение, которое является Omega (бесконечность). В качестве чисто математического алгоритма механизм регулярных выражений был бы слишком сложным для выполнения любого формального асимптотического анализа (кроме того, что такой анализ был бы в основном бесполезным).
Скорость роста конкретного выражения (так как это, во всяком случае, представляет собой алгоритм), будет гораздо более значимым, хотя и не обязательно более легким для анализа.
Сложность больше зависит от природы самого регулярного выражения, чем от длины строки. – LukeH 2010-12-07 15:40:27
@ LukeH Кроме того, это зависит от используемого языка программирования. Например, Python Regex никогда не может превышать мощность компьютера DFA, но Perl Regex может быть полным. – BlackVegetable 2013-04-30 20:40:08
Возможный дубликат [Сложность замены Regex] (http://stackoverflow.com/questions/21669/complexity-of-regex-substitution) – Kevin 2014-07-18 18:32:54