时间复杂度题 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 执行，而只会对可被 i 整除的 j 执行，因为这就是约束条件 j % i == 0 方法。由于 j ~ i*i，当最内层循环被执行时，只有 i 种情况。因此，内部循环中的迭代次数受 i^3 或简单的 n^3.

限制

结果

因此，整体时间复杂度为O(n⁴).

时间复杂度题 3 循环+if语句

Time complexity question 3 loops + if statement

for-loop

time-complexity

外循环

内循环

结果