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 (бесконечность). В качестве чисто математического алгоритма механизм регулярных выражений был бы слишком сложным для выполнения любого формального асимптотического анализа (кроме того, что такой анализ был бы в основном бесполезным).
Скорость роста конкретного выражения (так как это, во всяком случае, представляет собой алгоритм), будет гораздо более значимым, хотя и не обязательно более легким для анализа.
Смежные вопросы
- 1. Сложность замены регулярного выражения
- 2. Какова временная сложность следующего выражения?
- 3. Сложность получения регулярного выражения python для работы
- 4. временная сложность регулярного выражения в java
- 5. Сложность времени Конструкция DFA из регулярного выражения напрямую
- 6. Добавить сложность регулярного выражения для паролей в Sitecore 8
- 7. Регулярного выражения в Perl
- 8. Запись выражения регулярного выражения
- 9. Оптимизация выражения регулярного выражения
- 10. Оператор выражения регулярного выражения
- 11. выражение выражения регулярного выражения
- 12. Понятие выражения регулярного выражения
- 13. Выражения регулярного выражения Java
- 14. Создание выражения регулярного выражения
- 15. Выражения выражения слова регулярного выражения
- 16. Выражения выражения регулярного выражения Bash
- 17. Какова временная сложность string.GetHashCode?
- 18. Какова временная сложность кода?
- 19. Какова должна быть сложность
- 20. Какова сложность цикла while?
- 21. Какова сложность следующей грамматики
- 22. Какова временная сложность следующего?
- 23. Какова сложность следующего метода?
- 24. Какова сложность этого алгоритма
- 25. Какова временная сложность Collection.toArray()?
- 26. Какова сложность этой функции?
- 27. Какова сложность этих функций?
- 28. Какова сложность арифметической прогрессии?
- 29. Какова временная сложность этого?
- 30. Какова сложность этого алгоритма?
Сложность больше зависит от природы самого регулярного выражения, чем от длины строки. – 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