2个循环的复杂度，其中1个循环的复杂度

Question

for(int i=1;i<=n*n;i++)
{
   for(int j=1;j<=i/2;j++)
   {
         s=s+i+j;
   }
    k=1;
   while(k<j)
   {
        s=s+k;
        k=k*2;
   }
}

所以我知道复杂度为O（n ^ 4），但是我不太了解如何到达那里。我知道第一个循环具有n * n，因此更多。但是，另一个内部的2 for通常表示O（n ^ 2），由于第一个n * n，我只有（n ^ 2）^ 2。还是其中的两个fors分别表示n？第二个仅对偶数i和第三个相同的值运行，也许很重要。请帮忙。我很困惑，因为我记得一个例子，另一个for内部的2个fors是O（n ^ 2 * logn）。如果有人愿意解释一下，我将很感激。

Answer 1

所以您的第一个猜测几乎是正确的。 （i）的外部将进行n ^ 2次迭代。 （j）的内部在一次迭代中也将最多花费n ^ 2。在这种情况下，对于O表示法可以忽略。所以你有n ^ 2 x n ^ 2，那就是你的n ^ 4。