我想知道这个算法的复杂度是多少。N>=3 一个整数作为输入。谢谢 ！
initialisation : i=2
LOOP:
if N%i==0
return 1;
if i == [sqrt(N)]
return 0;
i= i + 1;
initialisation : i=2
LOOP:
if N%i==0
return 1; # 1 <-----
if i == [sqrt(N)]
return 0; # 2 <-----
i= i + 1;
情况 1：N 是偶数。然后我们就完成了O(1)- 参见第 ( # 1)行。或者 N 是奇数且非质数。然后当我们达到 N 的某个除数时就完成了（这会发生在平方根之前，或者同时发生）。
情况 2：N 是素数。然后我们将在完成之前点击[ n^0.5 ]数字（见行# 2）。
但是，正如@Lutzl 在他们的评论中指出的那样，精确计算可能会考虑所涉及的除法的运行时间。这有点不合适，因为我们不知道使用了什么乘法和除法算法。但是，总运行时间将O(max{a * sqrt(N), sqrt(N)})在那里O(a)是的运行时N % i == 0检查。我在这里假设实际的平方根计算实际上是恒定时间，并且只完成一次，这O(n^0.5)是因为这是算法结束前获得素数输入的迭代次数。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句