java - 为什么计算复杂度为O(n ^ 4)？

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++;
            }
        }
    }
}

我不明白当j = i，2i，3i时如何运行...最后一个for循环运行n次。我想我只是不明白我们是如何根据if语句得出这个结论的。

编辑:我知道如何计算所有循环的复杂性，除了为什么最后一个循环基于mod运算符执行i次...我只是不知道它是什么。基本上，为什么j％我不能上i * i而不是i？

最佳答案

让我们标记循环A，B和C:

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

循环A重复O(n)次。

循环B在A 的每次迭代中迭代O(i2)次。对于这些迭代中的每一个:

j % i == 0被评估，这需要O(1)时间。

在这些迭代的1/i中，循环C迭代j次，每次迭代执行O(1)工作。由于j平均为O(i2)，并且仅针对循环B的1/i迭代完成，因此平均成本为O(i2/i)= O(i)。

将所有这些都相乘得到O(n×i2×(1 + i))= O(n×i3)。由于i平均为O(n)，因此为O(n4)。

棘手的部分是说if条件仅在时间的1/i内为真:



实际上，j的确升至j < i * i，而不仅仅是j < i。但是条件j % i == 0仅当j是i的倍数时才为true。

范围内i的倍数是i，2*i，3*i，...，(i-1) * i。其中有i - 1，因此尽管循环B迭代了i - 1时间，但循环C达到了i * i - 1时间。