正则表达式的复杂度是什么？

Question

在字符串上执行正则表达式比较所需的复杂度如何随着字符串长度变化而变化？

- Ahmad Farid

---

正则表达式的复杂性取决于其本身的特性，而不是字符串的长度。 - LukeH

@LukeH 或者说，这取决于所使用的编程语言。例如，Python正则表达式永远无法超过DFA的计算能力，但Perl正则表达式可以是图灵完备的。 - BlackVegetable

可能是正则表达式替换的复杂度的重复问题。 - Kevin

Answer 1

答案取决于您对“正则表达式”的确切理解。经典的正则表达式可以编译成确定有限状态自动机，可以在O(N)时间内匹配长度为N的字符串。某些正则表达式语言的扩展会使情况变得更糟。您可能会对以下文件感兴趣：正则表达式匹配可以简单快速。

- NPE

---

我不确定是否有可能获取用于那篇文章的测试数据？我们工作场所一直在使用 Perl 正则表达式。如果它们真的那么慢，我们的硬件将完全失效。 - DeepDeadpool

你能澄清一下，“classic regexes”具体是什么意思吗？ - Varun Mathur

这是执行时间。那编译正则表达式呢？ - ThisCompSciGuy

@VarunMathur 一个经典的正则表达式可以完全通过串联、交替和 Kleene 星号 (*) 来实现。像 + 这样的运算符只是语法糖，不会增加正则表达式的表达能力。捕获表达式不是经典正则表达式的一部分，因为它们允许您匹配非正则语言（一个经典的例子是 (.*)x(\1)，它甚至不能描述上下文无关语言）。 - chepner

Answer 2

unbounded - 您可以创建一个在空输入字符串上永远不会终止的正则表达式。

- Alex Brown

---

好的，举个例子，Alex。 - JP19

Perl有特殊的代码来检测这种情况下的无限递归并退出，详细内容请参见"man perlre - "'foo' =~ m{ ( o? )* }x;"。 - Alex Brown

Answer 3

如果您使用普通的正则表达式（TCS：不带反向引用，连接，交替，Kleene星号），并且正则表达式已经编译，则时间复杂度为O(n)。

- royas

Answer 4

如果你正在寻找关于RegEx的紧密渐近界限（不考虑表达式本身），那么是没有的。正如Alex所指出的，您可以创建一个O（1）的正则表达式或一个Omega（无穷大）的正则表达式。作为纯数学算法，正则表达式引擎将过于复杂，无法执行任何形式的渐近分析（除了这种分析基本上毫无价值的事实之外）。

特定表达式的增长率（因为它实际上构成了一种算法）会更有意义，尽管不一定更容易分析。

- Adam Robinson

---

这是考虑到正则表达式的扩展。涉及常规结构的正则表达式（例如没有前瞻/后瞻模式）可以证明在任何输入上始终以O（输入字符串长度）的时间终止。 - Clément

@clement 即使大多数扩展也不能将正则表达式推进DFA之外。例如，Python Regex始终可以被建模为DFA。但是，一旦您开始使用Perl regex（我相信JavaScript也是如此），它就变成了一个等价于TM的不同动物。 - BlackVegetable

嗯，不是这样的。一个真正正则表达式的复杂度是被明确定义的。 - Charlie Martin