Menu
What is the complexity with respect to the string length that takes to perform a regular expression comparison on a string?
312
Time Complexity of Regex is O(MxN).
Regular expressions are dense. This makes them hard to read, but not in proportion to the information they carry. Certainly 100 characters of regular expression syntax is harder to read than 100 consecutive characters of ordinary prose or 100 characters of C code.
Regex is faster for large string than an if (perhaps in a for loops) to check if anything matches your requirement.
Regexs can only parse regular grammers anything context-free and higher you need a stack (i.e. a real parser). That is their only real limitation, performance depends the particular implementation, but generally is slow even precompiled compared to a state machine.
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.
52
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
