c - 为什么以Big Oh表示法将此代码视为O(N ^ 6)？

我只是在阅读another 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)。有人可以为我分解吗？

最佳答案

实际上是:

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)。

关于c - 为什么以Big Oh表示法将此代码视为O(N ^ 6)？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/6771342/