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 次。
最佳答案
这是因为循环 #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)
时间内。
关于c - 三重嵌套循环的时间复杂度?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14655627/