c++ - 以下代码段的复杂度 : log log n or log n?

Question

我认为下面的代码是 O(log log n) 因为它里面有 i*i 但我对 log n 感到困惑> 和 log (log n)。

for (i=2; i*i<=number; i++) 
{
   if (number % i == 0) return 0;
}

Answer 1

你的循环条件等同于 i <= sqrt(number) 所以在最坏的情况下你将有大约 sqrt(number) 次迭代。

所以这段代码的复杂度是O(√n) (O(sqrt(n))