[已解决]关于算法的时间复杂度计算问题

SKY_DOR/cy

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）、请问我的思路错在哪？

最佳答案

月排行榜 / 总排行榜

lyjlyj

2018-2-21 16:02:33

SKY_DOR/cy 发表于 2018-2-22 10:39
谢谢你细心的解答，按你的思路，答案算出来了~

但是为什么只算内层循环的循环次数？

如果内层循环中j=0，时间复杂度就是n*n，其实就是算内层循环的总次数
外层循环为n次、，在每一次中，内层循环都执行了n次，内层循环总的执行次数就是n*n
如果非要按你的计算方法，你可这样理解，外层循环不变，就是n次，而内层循环只要算出平均数就行了，也就是（n-1)/2所以就是n*（n-1）/2

跳转到最佳答案楼层

lyjlyj

SKY_DOR/cy 发表于 2018-2-22 10:39
谢谢你细心的解答，按你的思路，答案算出来了~

但是为什么只算内层循环的循环次数？

如果内层循环中j=0，时间复杂度就是n*n，其实就是算内层循环的总次数
外层循环为n次、，在每一次中，内层循环都执行了n次，内层循环总的执行次数就是n*n
如果非要按你的计算方法，你可这样理解，外层循环不变，就是n次，而内层循环只要算出平均数就行了，也就是（n-1)/2所以就是n*（n-1）/2

lyjlyj

你的思路我看不懂，简单的思路如下
当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-1  n   n-n

SKY_DOR/cy

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分别为外层循环和内层循环的总次数）

SKY_DOR/cy

lyjlyj 发表于 2018-2-22 11:00
如果内层循环中j=0，时间复杂度就是n*n，其实就是算内层循环的总次数
外层循环为n次、，在每一次中，内 ...

茅塞顿开，豁然开朗！
太感谢你了！