<分区>
考虑代码:
void foo(int n){
int s = 0;
for (i=1; i<=n; i++)
for(j=1;j<=i*i;j++)
if (j % i == 0){
for (k=1; k<=j; k++)
s++;
}
}
我们如何计算上述具有三个嵌套依赖循环的代码片段的时间复杂度？
我觉得
i 将运行到 n，
j 到 i2 或 n2，
k 到 j 或 n2。
所以根据我的说法，时间复杂度应该是 O(n*n2*n2) 或 O(n5)。但我知道它的 O(n4)。我哪里错了？