从两个方面对你的问题进行解答:
1.实验。令x=0,y=1,每运行一次x=x+y,x都会加1,所以最后x的值就是其运行值。测试程序如下:
运行结果:
2、从理论说明。外层给定一个n,内部两层就会循环1+2+3+....+n次,所以总的循环次数为:1+(1+2)+(1+2+3)+(1+2+3+4)+.....(1+2+3+4+.....+n).这个结果等于多少呢?请看下面数学证明。
证明过程:
数列各项是:1
1+2
1+2+3
……
1+2+3+……+N
由于:
1+2+3+……+N=N(N+1)/2=(N²+N)/2
1²+2²+……N²=N(N+1)(2N+1)/6
所以数列各项加起来就是:
S(N)=(1²+1)/2+(2²+2)/2+(3²+3)/2+……+(N²+N)/2
=[(1²+2²+3²+……+N²)+(1+2+3+……+N)]/2
=[N(N+1)(2N+1)/6+N(N+1)/2]/2
=N(N+1)[(2N+1)/6+1/2]/2
=N(N+1)(N+2)/6
综上,结果为N(N+1)(N+2)/6,时间复杂度为O(N的立方)