为什么计算复杂度为O（n^4）？

java big-o

2022-08-31 20:16:59

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...最后一个循环运行 n 次。我想我只是不明白我们是如何根据这句话得出这个结论的。forif

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

答案 1

让我们标记循环 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（i^{） 2} 次。对于这些迭代中的每一个：
- j % i == 0被评估，这需要 O（1）时间。
- 在这些迭代的 1/i 上，循环 C 迭代 j 次，每次迭代执行 O（1）工作。由于 j 平均为 O（i²），并且仅针对循环 B 的 1/i 迭代完成，因此平均成本为 O（i² / i） = O（i）。

将所有这些相乘，我们得到O（n × i² ×（1 + i））= O（n × i³）。由于 i 是平均 O（n），所以这是 O（n⁴）。

其中棘手的部分是说条件只为1 / i的时间：if

基本上，为什么j % i不能上升到i * i而不是i？

事实上，确实上升到，而不仅仅是达到。但条件为真，当且仅当是的倍数。jj < i * ij < ij % i == 0ji

范围内的倍数为、、、 ...、。有这些，所以尽管循环B迭代了时间，但循环C到达时间。ii2*i3*i(i-1) * ii - 1i - 1i * i - 1

答案 2

第一个循环使用迭代。n
第二个循环使用迭代。想象一下，当，然后 .n*ni=nj=n*n
第三个循环使用迭代，因为它只执行次数，在最坏的情况下，迭代是有界限的。niin

因此，代码复杂度为 O（n×n×n×n）。

我希望这有助于您理解。