algorithm - 这段代码的时间复杂度是多少？ O(n) 或 O(logn*logn)

Question

for(int i=1;i*i<N;i++)
{
    for(int j=1;j*j<N;j++)
    {
     // print something
    }
}

我的书显示答案是 O(n)。我觉得应该是O(logn^2)。

为什么答案是 O(n)？

Answer 1

外层循环遍历 i for i=1,2,...,sqrt(N)，内层循环相同；所以你总共得到 O(sqrt(N)*sqrt(N)) 也就是 O(N)。