例如，在下面给出的代码中，正则表达式方法的时间复杂度是多少：

Question

import re

for _ in range(int(input())):

s=input()                                      #input alphanumeric string 

print(sum(map(int,re.findall('\d+',s))))

Answer 1

此模式的findall的时间复杂度应为O（len（s）） 正则表达式不是回溯的，所以它应该可以在线性时间内进行匹配。 然而，我不知道re的实现，但如果它在线性时间上不匹配，我会感到惊讶

Answer 2

这应在线性时间O（n）内运行。检查与正则表达式的时间复杂性相关的问题

What is the complexity of regular expression?

What's the Time Complexity of Average Regex algorithms?

Answer 3

时间复杂度很难说，因为大多数正则表达式都是在正则语言上形成的。现在所有的正则语言都有其有限自动机，它可以用DFA、NFA或e-NFA来表示。一个正则表达式需要多长时间不仅取决于要匹配的模式的大小，还取决于计算该正则表达式的有限自动机。它也可能取决于实际发动机。如果它直接构造DFA，那么每次在输入字符串上匹配时，其长度上限为（O（n））