一个for循环的时间复杂度一定是o(n)吗?该怎么处理

一个for循环的时间复杂度一定是o(n)吗?
#include<iostream>
#define N 5
using namespace std;
void main()
{
int a[N]={1,2,3,4,5},b[N]={1,1,1,1,1};
int i,j=0;
for(i=0;i<=N;i++)
{
if(i==N)
{
cout<<b[j]<<endl;
i=0;
j++;
}
if(j==N) break;
if(i!=j) b[j]=a[i]*b[j];
}
}
那这个的时间复杂度是多少呢?o(n)还是o(n^2)?
[解决办法]

引用:

Quote: 引用:

o(n)。　　　。

 为什么呢 能深入分析下吗?循环体实际执行的次数是5*4呀

你没错。这for里j和i本质上构成了一个N进制的2位数，只有当j*N+i>=N^2的时候才退出。复杂度的确是O(n^2)。
[解决办法]
O(n^2)
[解决办法]
这个。。是O(n^2)的吧。。你的跟这个是等价的。。

for(int j = 0; j < N; ++j){
for(int i = 0; i < N; ++i){
if(i != j) b[j] *= a[i];
}
cout<<b[j]<<endl;
}

[解决办法]

引用:

Quote: 引用:

o(n)。　　　。

 为什么呢 能深入分析下吗?循环体实际执行的次数是5*4呀

好吧。。你在循环体里重设了i=0了，，，，我错了

查看更多 下一篇