Question

数据结构语句频度计算

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】