ruby - regex - 这个用于素数检测的正则表达式的复杂性是多少？

Question

这行 ruby​​ 代码检测素数（太棒了！）。

("1" * n) !~ /^1?$|^(11+?)\1+$/   # where n is a positive integer

此博客文章中解释了详细信息http://www.noulakaz.net/weblog/2007/03/18/a-regular-expression-to-check-for-prime-numbers/

我很好奇它以 BIG-O 符号的方式表现。有人帮忙吗？

Answer 1

从经验数据来看，它似乎是O(n ² )。

我在前 10000 个素数的每 100 个上运行一次 Ruby 代码。结果如下：

蓝点是记录的时间，橙色线是y = 2.9e-9 * x^2。这条线完美地拟合了数据，表明复杂度为 O(n ² )。

这是意料之中的，因为正则表达式会检查所有可能的除数以查看它们中的任何一个是否在字符串中出现了整数次。