如何计算三个嵌套依赖循环的时间复杂度？

Question

考虑代码：

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 直到 i² 或 n², k 到 j 或 n².

所以时间复杂度应该是O(n*n²*n²) 或者, O(n ⁵) 根据我的说法。但我知道它的 O(n⁴)。我哪里错了？

Answer 1

这一行： 如果 (j % i == 0) 正在发挥作用。 例如，对于 i=3 ， j 将 运行 9 次。

and (j % i == 0) 只有 3 次为真。因此，k 循环不会 运行 9 次，而只会 3 次。

Answer 2

每当 j 是 i 的倍数时，将执行最内层循环。 在这个循环中 j 将是 i 的倍数，i 次。

现在我们考虑每个 i 迭代。只有 i-1 次我们将执行 if 检查 only.And 然后休息时间我们将 运行 内部循环 ij 次（我们也做了循环检查）。

i 次迭代的工作量为 i+ij。 j 与 1..i 不同，因此结果将是 i^2+ (i^2*(i+1)/2)。

现在，如果我们考虑外部循环，它将是 i=1..n Sum(i^2+ (i^2*(i+1)/2)) ~ O(n^4)。