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

Question

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 而不是 i？

Answer 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 ² ) 次。对于这些迭代中的每一个：
  • 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 ⁴ )。

棘手的部分是说if条件仅在 1/ i 次为真：

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

事实上，j确实高达j < i * i，而不仅仅是高达j < i。但条件j % i == 0为真当且仅当j是 的倍数i。

i范围内的倍数是i, 2*i, 3*i, ..., (i-1) * i。有i - 1这些，所以i - 1尽管循环 B 迭代i * i - 1次数，循环 C 达到次数。

Answer 2

• 第一个循环消耗n迭代。
• 第二个循环消耗n*n迭代。想象一下当 时的情况i=n，然后j=n*n。
• 第三个循环消耗n迭代，因为它只执行了i几次，在最坏的情况下i有界n。

因此，代码复杂度为 O(n×n×n×n)。

我希望这有助于你理解。

Answer 3

所有其他答案都是正确的，我只想修改以下内容。我想看看，如果减少内部 k 循环的执行次数是否足以降低下面的实际复杂性，O(n?).所以我写了以下内容：

for (int n = 1; n < 363; ++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++;
                }
            }
        }
    }

    long cubic = (long) Math.pow(n, 3);
    long hypCubic = (long) Math.pow(n, 4);
    double relative = (double) (sum / (double) hypCubic);
    System.out.println("n = " + n + ": iterations = " + sum +
            ", n³ = " + cubic + ", n? = " + hypCubic + ", rel = " + relative);
}

执行此操作后，很明显，复杂性实际上是n?。输出的最后几行如下所示：

n = 356: iterations = 1989000035, n³ = 45118016, n? = 16062013696, rel = 0.12383254507467704
n = 357: iterations = 2011495675, n³ = 45499293, n? = 16243247601, rel = 0.12383580700180696
n = 358: iterations = 2034181597, n³ = 45882712, n? = 16426010896, rel = 0.12383905075183874
n = 359: iterations = 2057058871, n³ = 46268279, n? = 16610312161, rel = 0.12384227647628734
n = 360: iterations = 2080128570, n³ = 46656000, n? = 16796160000, rel = 0.12384548432498857
n = 361: iterations = 2103391770, n³ = 47045881, n? = 16983563041, rel = 0.12384867444612208
n = 362: iterations = 2126849550, n³ = 47437928, n? = 17172529936, rel = 0.1238518469862343

这表明，n?该代码段的实际复杂度和复杂度之间的实际相对差异是一个趋近于大约0.124...（实际上是 0.125）的值的因子。虽然它没有给我们确切的值，但我们可以推断出以下内容：

时间复杂度是你的函数/方法n?/8 ~ f(n)在哪里f。

• Big O 符号的维基百科页面在“巴赫曼-朗道符号家族”表中指出，~定义两个操作数边的极限是相等的。或者：

  f 渐近地等于 g

（我选择 363 作为排除的上限，因为这n = 362是我们得到合理结果的最后一个值。之后，我们超出了长空间，相对值变为负数。）

用户 kaya3 得出以下结论：

顺便说一下，渐近常数正好是 1/8 = 0.125；这是 Wolfram Alpha 的确切公式。