为什么这个代码在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).