c - 三重嵌套循环的时间复杂度？

Question

for(i=0; i<n; i++)
{
    a[i]=0;
    for(i=0; i<n; i++)
    {
        for(j=0; j<n; j++)
        {
            a=3;
        }
    }
}

这是一个三重嵌套循环。我的书指出运行时间是:O(N) + O(N^2) = O(N^2)

不应该是O(N^3)吗？所有 3 个循环都相互依赖。它将运行 N*N*N 次。

Answer 1

这是因为循环 #1 和循环 #2 在比较期间使用相同的计数变量 i。

在使用 i 的第二个循环结束时，i 的值为 n 这使得它跳出外层循环，如下所示出色地。 那里的一个循环是完全多余的。

---

#include <stdio.h>
int main(){
    int x = 0;
    int n = 20;
    int i, j;
    for(i=0; i<n; i++) //this loop runs once
    {
        for(i=0; i<n; i++) //this loop runs n times
        {
            for(j=0; j<n; j++) //this loop also runs n times
            {
                x++;
            }
        }
    }
    printf("%d", x);
}

整个运行在 O(N^2) 时间内。

Example