Qual è la complessità dell’espressione regolare?

Qual è la complessità rispetto alla lunghezza della stringa necessaria per eseguire un confronto di espressioni regolari su una stringa?

La risposta dipende da cosa intendi esattamente per “espressioni regolari”. Le regex classiche possono essere compilate in automi finiti deterministici che possono corrispondere a una stringa di lunghezza N in tempo O(N) . Alcune estensioni del linguaggio regex cambiano la situazione in peggio.

È ansible trovare il seguente documento di interesse: la corrispondenza delle espressioni regolari può essere semplice e veloce .

illimitato – puoi creare un’espressione regolare che non termina mai, su una stringa di input vuota.

Se si usa il normale (TCS: nessun riferimento, concatenazione, alternanza, stella di Kleene) regexp e regexp è già compilato, quindi è O (n).

Se stai cercando limiti stretti asintotici su RegEx (senza rispetto per l’espressione stessa), allora non ce n’è uno. Come sottolinea Alex, puoi creare un’espressione regolare che è O (1) o un’espressione regolare che è Omega (infinito). Come un algoritmo puramente matematico, un motore di espressioni regolari sarebbe troppo complicato per eseguire qualsiasi tipo di analisi asintotica formale (a parte il fatto che tale analisi sarebbe sostanzialmente priva di valore).

Il tasso di crescita di una particolare espressione (dal momento che, in realtà, costituisce un algoritmo, comunque) sarebbe molto più significativo, anche se non necessariamente più facile da analizzare.