What is the complexity of regular expression?

What is the complexity with respect to the string length that takes to perform a regular expression comparison开发者_运维技巧 on a string?

---

The answer depends on what exactly you mean by "regular expressions." Classic regexes can be compiled into Deterministic Finite Automata that can match a string of length N in O(N) time. Certain extensions to the regex language change that for the worse.

You may find the following document of interest: Regular Expression Matching Can Be Simple And Fast.

---

unbounded - you can create a regular expression that never terminates, on an empty input string.

---

If you use normal (TCS:no backreference, concatenation,alternation,Kleene star) regexp and regexp is already compiled then it's O(n).

---

If you're looking for tight asymptotic bounds on RegEx (without respect to the expression itself), then there isn't one. As Alex points out, you can create a regex that is O(1) or a regex that is Omega(infinity). As a purely mathematical algorithm, a regular expression engine would be far too complicated to perform any sort of formal asymptotic analysis (aside from the fact that such analysis would be basically worthless).

The growth rate of a particular expression (since that, really, constitutes an algorithm, anyway) would be far more meaningful, though not necessarily any easier to analyze.