我想知道这个寻找素数的简单算法的渐近复杂度是否为 O(n):
PrimeNumber(n)
Int i;
If (n%2=0) then { return "not prime"; }
Else {
For(i=3;i<(√n)+1;i=i+2;){
If (n%i=0) then {return "not prime";}
}
}
return "prime";
最佳答案
时间复杂度为 O(sqrt(n))
,因为循环自身迭代了 (sqrt(n)+1-3)/2
次,这在O(sqrt(n))
。
请注意,由于 O(sqrt(n))
是 O(n)
的子集,所以这样说也是正确的是 O(n)
- 但这个界限并不严格。
关于algorithm - 寻找素数的简单算法的复杂性,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44072198/