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

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 ²).

这是预期的,因为正则表达式检查所有可能的除数,以查看它们中的任何除数是否在字符串中出现了整数次.