关于算法的时间复杂度计算问题
void fun(int n){
int i,j,x=0;
for(i=0;i<n;++i)
for(j=i+1;j<n;++j)
++x;
}
（1）、请问这道题的时间复杂度从数学的角度具体如何计算
答案是：f（n）=n(n-1)/2
求详细的数学运算过程
我的思路是，因为循环嵌套，所以
总运算次数 M=m1*m2（m1，m2分别为为外层循环的次数和内层循环的次数）
外层循环规模为 n=m1^2/2
内层循环规模为j1=m1+1;
jm2=(m1+1)+(m2-1)*1
则内层循环规模为：n=[(j1+jm2)m2]/2
最后算出m1、m2都是带根号的，且n在根号里面
M=m1*m2算出来答案不是f（n）=n(n-1)/2
（2）、请问我的思路错在哪？ SKY_DOR/cy 发表于 2018-2-22 10:39
谢谢你细心的解答，按你的思路，答案算出来了~
但是为什么只算内层循环的循环次数？
如果内层循环中j=0，时间复杂度就是n*n，其实就是算内层循环的总次数
外层循环为n次、，在每一次中，内层循环都执行了n次，内层循环总的执行次数就是n*n
如果非要按你的计算方法，你可这样理解，外层循环不变，就是n次，而内层循环只要算出平均数就行了，也就是（n-1)/2所以就是n*（n-1）/2
你的思路我看不懂，简单的思路如下
当i=0，j=1，++x执行了n-1次
当i=1，j=2，++x执行了n-2次
如此类推
如下所示，总的执行次数就是(n-1)+(n-2)+(n-3)+...+(n-n) = n(n-1)/2
i j 运算次数
0 1 n-1
1 2 n-2
2 3 n-3
. . .
n-1n n-n
lyjlyj 发表于 2018-2-21 17:22
你的思路我看不懂，简单的思路如下
当i=0，j=1，++x执行了n-1次
当i=1，j=2，++x执行了n-2次
谢谢你细心的解答，按你的思路，答案算出来了~
但是为什么只算内层循环的循环次数？
我想，既然循环嵌套那么总的循环次数应该是 外层循环的次数*内层循环的次数
因为 外层循环循环一次那么内层循环就要循环m2次
所以才有M=m1*m2（m1，m2分别为外层循环和内层循环的总次数） lyjlyj 发表于 2018-2-22 11:00
如果内层循环中j=0，时间复杂度就是n*n，其实就是算内层循环的总次数
外层循环为n次、，在每一次中，内 ...
茅塞顿开，豁然开朗！
太感谢你了！
页:
[1]