为什么这段代码在 Big Oh 表示法中被视为 O(N^6)？

Question

我刚刚阅读另一个问题，这段代码引起了我的兴趣：

for(i = 0; i < n; i++)
{
    for(j = 0; j < i*i; j++)
    {
        for(k = 0; k < i*j; k++)
        {
            pseudo_inner_count++;
            for(l = 0; l < 10; l++);
        }
    }
}

我不明白这是怎么做到的为 O(N^6)。有人可以帮我分解一下吗？

Answer 1

实际上是这样的：

• i 循环迭代了 O(N) 次，所以 i 的值为 O(N)，所以我们可以说 O(I)=O(N)。
• j 循环迭代 O(I^2) = O(N^2) 次（单独考虑时，没有外部循环）。
• k 循环迭代 O(I*J) = O(N*N^2) = O(N^3) 次。
• l 循环仅迭代 10 次，因此时间复杂度为 O(1)。

循环是嵌套的，所以我们必须将它们相乘（你明白为什么吗？）。总计为 O(N)*O(N^2)*O(N^3) = O(N^6)。

Answer 2

是

第一个循环 n
n² 用于第二个循环
第三个循环的 n3

内循环为 O(1)

总共为 O(n⁶)。

第三个循环是 n3 的原因是，当你考虑它时，j 达到 n2，i 达到 n，所以 i*j 达到 n3。

Answer 3

我会说：

• n 代表第一个循环
• n² 代表第二个循环 => 第三次循环的n3 n2 总数
• =>总共 n⁵
• 又一个 n 循环 =>总计 n⁶