algorithm - 寻找素数的简单算法的复杂性

Question

我想知道这个寻找素数的简单算法的渐近复杂度是否为 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";

Answer 1

时间复杂度为 O(sqrt(n))，因为循环自身迭代了 (sqrt(n)+1-3)/2 次，这在O(sqrt(n))。

请注意，由于 O(sqrt(n)) 是 O(n) 的子集，所以这样说也是正确的是 O(n) - 但这个界限并不严格。