Question

数据结构中关于语句频度计算

计算下列程序段中X＝X＋1的语句频度
for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
for(k=1;k<=j;k++)
x=x+1;

谢谢拉！！！！！！！
以下是我发消息问kanerry这个题目，他真是一个非常热心的人，非常感谢他．这题我想了几天都不会做，还好他教会我了．呵呵

计算下列程序段中X＝X＋1的语句频度
for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
for(k=1;k<=j;k++)
x=x+1;
这个你的回答我看的不是太懂．．可不可以再说详细一点啊！谢谢了

--------------------------------------------------------------------------------
这题目确实较复杂
具体有递归公式
An=An-1+n*(n+1)/2 //计算次数
A1=1

比如
i=1 ,j=1,k=1//得出A1=1,也就是i=1时只执行一次
i=2,j=1,k=1
i=2,j=2,k=1
i=2,j=2,k=2//也就是i=2时会执行3次，就是(1+2),因此A2=A1+3=4
这里就得出规律
i=n时 会执行 n(n+1)/2次

也就是An=An-1+n*(n+1)/2 //计算次数

因此An=1/2(∑(n^2)+∑n) //这里是级数求和了，固定公式，我只是套上去罢了
=1/2(n(n+1)(2n+1)/6+n(n+1)/2)
=n(n+1)(n+2)/6

所以时间复杂度是O(n^3)

回复此消息

Answer 1

1、首先时间复杂度定义，如下图所示。

2、在大多数情况下，原操作是最深层循环内的语句的原操作，他的执行次数和包含他的语句的频度相同。

3、以上三例都含有基本操作“x++”但频度各有不同。

4、时间复杂度分别为，常量阶、线性阶、平方阶。

5、最后计算时间复杂度，函数中的常数和其他次要项常常可以忽略，而更应该关注主项（最高项的阶数）。

Answer 2

具体有递归公式
An=An-1+n*(n+1)/2 //计算次数
A1=1

因此An=1/2(∑(n^2)+∑n)
=1/2(n(n+1)(2n+1)/6+n(n+1)/2)
=n(n+1)(n+2)/6

所以时间复杂度是O(n^3)

Answer 3

[(m-1)*(2+m)]/2