正则表达式替换的复杂性问题接近问题，但并不相同。根据theprise的回复，（DFA引擎的）复杂度是：
O(2^m + n) [其中 m 是正则表达式的长度，n 是字符串的长度]
红皮书《算法设计手册》第15-16页讨论了不同算法的时间。据此，当算法长度超过 1,000,000 时，O(m^2) 的算法就没有希望了。处理时间为 16.7 分钟，假设运算时间为 1 纳秒。
书中的陈述增加了我的兴趣。你能在 16.7 分钟的处理时间内完成 1,000,000 个字符的正则表达式吗？你能做一个灾难性的正则表达式并且处理时间仍然存在吗？我真的很怀疑。
多项式时间内运算时间为一纳秒的最长可能正则表达式是多少？
这是一个毫无意义的问题。正则表达式不是一种算法，它们是一种语言。这种语言的许多实现都有自己的性能特征，每个单独的正则表达式都有自己的成本。例如，交替/(a|b|c)/是一个可并行化的问题，因此并行执行表达式的引擎将比那些不并行执行的引擎具有更好的性能。
This is similar to asking what is the best case for sorting. Some people will tell you O(n log n), but they would be wrong. There answer depends on the algorithm used. There are some sorts (such as radix sort) that have a worst case of O(n).
实际的复杂性可能取决于特定的正则表达式。1000000 'a 的简单匹配大约需要 10 秒：
import re
expr = 'a' * 1000000
re.match(expr, expr)
这种情况下的复杂度似乎约为 O(m)，但更复杂的表达式肯定会花费更长的时间。