質問正規表現置換の複雑さ は質問に近づいていますが、同じではありません。theprise の返信によると、(DFA エンジンの) 複雑さは次のとおりです。
O(2^m + n) [m は正規表現の長さ、n は文字列の長さ]
15-16 ページの赤い本「アルゴリズム設計マニュアル」では、さまざまなアルゴリズムの時間について説明しています。それによると、アルゴリズムの長さが 1,000,000 を超えると、O(m^2) のアルゴリズムは絶望的です。1ナノ秒の動作時間を想定すると、処理に16.7分かかります。
その本の声明は私の興味を増大させた. 1,000,000 文字の長さの正規表現を 16.7 分の処理時間で実行できますか? 壊滅的な正規表現を実行しても、処理時間は維持できますか? 私は本当にそれを疑います。
多項式時間で 1 ナノ秒の演算時間が可能な最長の正規表現は?
これは無意味な質問です。正規表現はアルゴリズムではなく、言語です。この言語には多くの実装があり、すべてに独自のパフォーマンス特性があり、個々の正規表現には独自のコストがあります。たとえば、交互/(a|b|c)/化は並列化可能な問題であるため、式を並列に実行するエンジンでは、そうでないエンジンよりもパフォーマンスが向上します。
これは、並べ替えの最良のケースを尋ねるのと似ています。一部の人々はあなたに言うでしょうO(n log n)、しかし彼らは間違っているでしょう。答えは、使用するアルゴリズムによって異なります。最悪の場合の。のいくつかのソート（基数ソートO(n)など）があります。
実際の複雑さは、おそらく特定の正規表現に依存します。1000000 'a's の単純な一致には、約 10 秒かかります。
import re
expr = 'a' * 1000000
re.match(expr, expr)
この場合の複雑さは約 O(m) のように見えますが、より複雑な式は確かに時間がかかります。