[求助]时间复杂度,问题
for(i=2;i<=n;++I)for(j=2;j<=i-1;++j)
{++x;a[i,j]=x;}
为什么:
语句频度为:
1+2+3+…+n-2=(1+n-2) ×(n-2)/2
=(n-1)(n-2)/2
=n2-3n+2
求解????解释下
当循环变量为i时,j要循环i-2次(循环体,x++的操作次数),而i是从2到n的.所以将他们相加得到.
0+1+2+....+n-2;
而复杂度是n^2级的.
当变量为i时候,j不是循环i-1次吗,怎么会成为i-2次啊
“0+1+2+....+n-2”只是i循环的次数啊,还有j循环,怎么理解啊
如果是for(i=2;i<=n;i++)
{++x;s+=x;}
那么语句频度是:2(n-1)吧(因为,i执行一次,++x和s+=x各执行一次,所以是2(n-1),对吗?)
那么上面那题为什么是0+1+2+....+n-2
i的循环次数只有n-2+1次.而j的循环是由i来决定的.只有把内循环体的执行次数相加才是程序的复杂度.所以总次数为0+1+2+...+n-2(i依次代2...n得到).