这行 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符号性能很感兴趣，有人可以帮忙吗？
正则表达式 - 检测质数的这个正则表达式的复杂度是什么？
6
这篇博客http://www.noulakaz.net/weblog/2007/03/18/a-regular-expression-to-check-for-prime-numbers/详细说明了相关细节。我对它的BIG-O符号性能很感兴趣，有人可以帮忙吗？
- Alston
4
1博客评论已经谈到了性能问题，即使在稍微大一些的数字下，它也会开始严重受损。这个评论似乎很恰当： “所以一个32位的数字2147483648将占用半个G的内存。” - ydaetskcoR
就正则表达式的巧妙使用而言，它在复杂性方面比仅使用最简单的质数算法更糟糕！ - micantox
无论如何，我想看到由该正则表达式生成的FSM。在我看来，它应该是O（N），其中N是数字的大小，而其他算法通常是O（sqrt（N））IIRC。更不用说它在空间方面也是O（N），这使得它对于大的N不可行。（显然，在ruby中它是O（N）空间方面**，因为可以在C ++中实现一个范围，该范围可与正则表达式匹配，但不会占用N个字节'1'）:-D - Massa
当n=1时，这个不起作用，因为1是质数。 - canoe
1个回答
5
根据经验数据，它的复杂度为O(n^2)。
我在前10000个素数中的每100个运行了Ruby代码。以下是结果：
蓝色点是记录的时间，橙色线是y = 2.9e-9 * x ^ 2。该线完全符合数据，表明复杂度为O(n^2)。
这是可以预料的，因为正则表达式检查所有可能的因子，以查看它们是否在字符串中出现整数次数。
我在前10000个素数中的每100个运行了Ruby代码。以下是结果：
蓝色点是记录的时间，橙色线是y = 2.9e-9 * x ^ 2。该线完全符合数据，表明复杂度为O(n^2)。
这是可以预料的，因为正则表达式检查所有可能的因子，以查看它们是否在字符串中出现整数次数。
- tom
2
难道减速不是来自内存分配，而是正则表达式应用吗？ - Massa
我再次运行它，内存使用量仅约为4MB。 - tom
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接