Question

求讲解： for(i=1;i<n;i++) { for(j=i;j<=n;j++) { x++; } } 1.语句x++的执行频度 2.该算法的时间复杂度

Answer 1

n=1时X++执行n次;
n=2时X++执行n-1次;
........
n=n-1时X++执行2次;
n=n时X++执行1次;
综上所述X++执行的频度时1～n的等差和(n2+n)/2

算法时间复杂度O(n2);

追问

讲的细一点，书上也是这样写的
n=2时怎么就成n-1次了，等差数列是怎么来的

追答

Sorry, 中午说的有问题；
n=1时；X++ 执行1次
for(i=1;i<=1;i++)
{
for(j=i;j<=1;j++)

{
X++;

}
}
n=2时；X++ 执行2+1次
for(i=1;i<=2;i++)// 这个会执行2次
{
for(j=i;j<=2;j++)//这个也执行3次，i=1是，j会从1~2，x++执行了两次，i=2是，j只执行2，X++执行了1次

{
X++;

}
}
.....
n=n-1时；X++ 执行(n-1)+(n-2)+..+2+1次
for(i=1;i<=n-1;i++)// 这个会执行n-1次
{
for(j=i;j<=n-1;j++)//这个(n-1)+(n-2)+..+2+1执行次，i=1是，j会从1~n-1，x++执行了n-1次，i=2时，j会从2~n-1，X++执行了n-2次.....i=n-2时，j会n-2~n-1执行2次,i=n-1时，j会n-1~n-1执行1次。
{
X++;

}
}

n=n时；X++ 执行n+(n-1)+(n-2)+..+2+1次
for(i=1;i<=n;i++)// 这个会执行n次
{
for(j=i;j<=n;j++)//这个n+(n-1)+(n-2)+..+2+1执行次，i=1是，j会从1~n，x++执行了n次，i=2时，j会从2~n，X++执行了n-1次.....i=n-1时，j会n-1~n执行2次,i=n-1时，j会n~n执行1次。
{
X++;

}
}