#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)?
8 个解决方案
#1
o(n)。 。
#2
为什么呢 能深入分析下吗?循环体实际执行的次数是5*4呀
#3
只计算最坏情况下运算的时间
#4
你没错。这for里j和i本质上构成了一个N进制的2位数，只有当j*N+i>=N^2的时候才退出。复杂度的确是O(n^2)。
#5
肯定不是。。
#6
O(n^2)
#7
这个。。是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;
}
#8
好吧。。你在循环体里重设了i=0了，，，，我错了
#1
o(n)。 。
#2
为什么呢 能深入分析下吗?循环体实际执行的次数是5*4呀
#3
只计算最坏情况下运算的时间
#4
你没错。这for里j和i本质上构成了一个N进制的2位数，只有当j*N+i>=N^2的时候才退出。复杂度的确是O(n^2)。
#5
肯定不是。。
#6
O(n^2)
#7
这个。。是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;
}
#8
好吧。。你在循环体里重设了i=0了，，，，我错了