for-loop - 时间复杂度问题 3 循环 + if 语句

Question

我很难找到下面代码的时间复杂度。我认为 if语句将运行大约 n次；然而，我无法用数学来描述它。提前致谢。

int sum = 0;

for (int i = 1; i < n; i++) {
    for (int j = 1 ; j < i*i; j++) {
        if (j % i == 0) {
            for (int k = 0; k < j; k++) {
                sum++;
            }
        }
    }
}

Answer 1

外环
嗯，很明显它是 O(n) 因为 i以 n 为界.
内循环
如果我们单独看第​​二个循环，那么它看起来如下:

...
for (int j = 1 ; j < i*i; j++){
...

j以 i*i 为界或者干脆 n^2 .
但是，不会为每个 j 执行最里面的循环。 ，但仅适用于 j可以被 i 整除的 s因为这就是约束 j % i == 0方法。自 j ~ i*i ，将只有 i在最里面的循环被执行的情况下。因此，内循环中的迭代次数受 i^3 的限制。或者干脆 n^3 .
结果
因此，总时间复杂度为 O(n4)。