Quelle est la complexité de l'expression régulière?

Question

Quelle est la complexité par rapport à la longueur de chaîne nécessaire pour effectuer une comparaison d'expression régulière sur une chaîne?

Answer 1

La réponse dépend surtout de ce que tu veux dire par "expressions régulières." Classique regexes peut être compilé en Automates Finis Déterministes qui peut correspondre à une chaîne de longueur N en O(N) du temps. Certaines extensions de la regex de changement de la langue que pour le pire.

Vous pouvez trouver le document suivant d'intérêt: Expression Régulière Correspondant Peut Être Simple Et Rapide.

Answer 2

illimité - vous pouvez créer une expression régulière qui ne se termine jamais, sur une chaîne d'entrée vide.

Answer 3

Si vous utilisez normal (TCS: pas de backreference, concaténation, alternance, étoile de Kleene) regexp et regexp est déjà compilé, alors c’est O (n).

Answer 4

Si vous êtes à la recherche d'un asymptotique des bornes sur les RegEx (sans égard à l'expression elle-même), il n'en est pas une. Comme Alex points, vous pouvez créer une regex qui est O(1) ou une regex qui est Omega(infini). Comme purement mathématique de l'algorithme, un moteur d'expression régulière serait beaucoup trop compliqué à réaliser toute sorte de formel, l'analyse asymptotique (à part le fait qu'une telle analyse serait essentiellement sans valeur).

Le taux de croissance d'une expression donnée (depuis que, vraiment, constitue un algorithme, de toute façon) serait beaucoup plus significatif, mais pas nécessairement plus facile à analyser.