三巢环的时间复杂度？

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,值为n,这使得它i也会突破外循环.一个循环在那里是完全冗余的.

#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)整个运行的时间.

例