1 for 循环内 2 for 循环的复杂度
Complexity of 2 for loops inside 1 for loop
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^2)^2，因为第一个 n * n?或者里面的两个 for 分别代表 n？第二个 for 仅针对 i 的偶数值运行，而第三个 for 相同，也许这很重要。请帮忙。我很困惑，因为我记得一些例子，其中 2 fors inside another for is O(n^2*logn)。如果有人愿意解释一下，我将不胜感激。
所以你的第一个猜测很正确。 (i) 的外部将进行 n^2 次迭代。 (j) 的内部在单次迭代中最多花费 n^2。 while 在这种情况下可以忽略（您可以使用 n^2 作为它的非常粗略的上限）。所以你有 n^2 x n^2 那就是你的 n^4.
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^2)^2，因为第一个 n * n?或者里面的两个 for 分别代表 n？第二个 for 仅针对 i 的偶数值运行，而第三个 for 相同，也许这很重要。请帮忙。我很困惑，因为我记得一些例子，其中 2 fors inside another for is O(n^2*logn)。如果有人愿意解释一下，我将不胜感激。
所以你的第一个猜测很正确。 (i) 的外部将进行 n^2 次迭代。 (j) 的内部在单次迭代中最多花费 n^2。 while 在这种情况下可以忽略（您可以使用 n^2 作为它的非常粗略的上限）。所以你有 n^2 x n^2 那就是你的 n^4.