此代码片段的时间复杂度是多少?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 i=1,2,...,sqrt(N)，内循环相同;所以总的来说，你得到O(sqrt(N)*sqrt(N))这是O(N)。