Question

x=0;for(i=1;i<n;i++) for(j=1;j<n-i;j++)x++的时间复杂度是多少

Answer 1

　　从两个方面对你的问题进行解答：

　　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的立方)

  
  

Answer 2

i=1时 循环n-1
i=2。。。n-2

i=n-1 .... 1
所以1+2+3+。。。n-1=(1+n-1)*（n-1）/2=n^2/2-n/2
所以时间复杂度是0(n^2)

Answer 3

应该是O(n2)，（n2表示n的平方……）