这个时间复杂度怎么求的?
那种每个循环都是从1到n的我知道怎么计算出来的,可这种就不知道了,请高手明示一下:
for (i=2;i<=n;++i){
for (j=2;j<=i-1;==j){
++x;
}
}
书上说这种时间复杂度是:(n-1)(n-2)/2,怎么计算出来的?
[解决办法]
[code=C/C++][/code]for (i=2;i <=n;++i){
for (j=2;j <=i-1;++j){
++x;
}
}
循环次数分别为
0
1
2
。。。
n-2
次数为n-1
所以为(0 + n -2)( n -1 )/2
[解决办法]
i=2,下面的for循环次数为0
i=3,下面的for循环次数为1
i=4,下面的for循环次数为2
……
i=n,下面的for循环次数为n-2
时间复杂度为:0+1+2+...+(n-2) = (n-1)*(n-2)/2