Question

数据结构，计算语句频度

for(i=1;i<=n;i++){
for(j=1;j<=i;j++){
for(k=1;k<=j;k++)
x+=delta; //这个语句的频度如何计算，求具体方法
}
答案是1/12[n(n+1)(2n+3)] 不懂怎么算出来的

Answer 1

对于上面的频度，因为是一个三重循环，所以列一个表给你吧,k表示语句@执行的次数：

i j k
1 1 1
2 1~2 1+(1+2)
3 1~3 1+(1+2)+(1+2+3)
4 1~4 1+(1+2)+(1+2+3)+(1+2+3+4)
. . .
. . .
. . .
n 1~n 1+(1+2)+(1+2+3)+(1+2+3+4)+....(1+2+...+n)

可以列出求和公式：Sn=∑(i=1~n) (i+1)*i/2=1/2*[(1+2+.....n)+(1^2+2^2+.......n^2)]
最后用等比数列球和公式和平方求和公式得出语句@的频度为:(n+2)*(n+1)*n/6

【答案转自SGetEternal】