¿Cuál es la complejidad de la expresión regular?

¿Cuál es la complejidad con respecto a la longitud de cadena que lleva a realizar una comparación de expresión regular en una cadena?

La respuesta depende de qué es exactamente lo que quiere decir con “expresiones regulares”. Las expresiones regulares clásicas se pueden comstackr en autómatas finitos deterministas que pueden coincidir con una cadena de longitud N en tiempo O(N) . Ciertas extensiones del lenguaje de expresiones regulares cambian eso para peor.

Puede encontrar el siguiente documento de interés: la coincidencia de expresión regular puede ser simple y rápida .

ilimitado: puede crear una expresión regular que nunca finaliza en una cadena de entrada vacía.

Si usa normal (TCS: sin referencia, concatenación, alternancia, estrella de Kleene), expresiones regulares y expresiones regulares ya están comstackdas, entonces es O (n).

Si está buscando límites asintóticos ajustados en RegEx (sin respeto a la expresión en sí), entonces no hay uno. Como señala Alex, puedes crear una expresión regular que sea O (1) o una expresión regular que sea Omega (infinito). Como un algoritmo puramente matemático, un motor de expresión regular sería demasiado complicado para realizar cualquier tipo de análisis asintótico formal (aparte del hecho de que dicho análisis sería básicamente inútil).

La tasa de crecimiento de una expresión particular (ya que, en realidad, constituye un algoritmo, de todos modos) sería mucho más significativa, aunque no necesariamente más fácil de analizar.