c - 为什么这段代码在 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² 代表第二个循环 n³ 代表第三个循环

内循环是 O(1)

总数为 O(n⁶)。

第三个循环是n³的原因是因为当您考虑它时，j到达n²并且i到达n，所以i * j到达n³。

Answer 3

我会说 ：

• n 代表第一个循环
• 第二个循环的 n² => n³ 的总数
• 第三个循环的 n² => 总共 n⁵</li>
• 又一个 n 循环 => 总共 n⁶</li>