下面这个3层循环的时间复杂度为什么是O（n^3）

Question

x=1;
for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
for(k=1;k<=j;k++)
x++; 　　
为什么
循环了(1^2+2^2+3^2+...+n^2)=n(n+1)(2n+1)/6≈(n^3)/3次
这个1^2+2^2+3^2是怎么得出来的

Answer 1

首先，我们考虑这么一种情况，当i取值为N的时候，那么我们上面那个三层循环就变成了
for(j=1;j<=N;j++)
for(k=1;k<=j;k++)
x++;
这样看来，是不是一目了然了。
N的取值为 1 2 3 4 5 ...... N-1 N
相应的，我们可以把上面那个二层for循环改写为一层循环
for(k=1;k<=[1 2 3 4 5 ......N-1 N];k++)
x++;
那么，我们这个for循环运行的总的时间复杂度就是 (1+n)n/2
当然，这不是最终的时间复杂度，因为我们只是讨论了i取a的情况
所以，总的时间复杂度为 Σ（对i求和 i从1到n）i+i^2/2

一次循环： 运行为N次；
二次循环：运行为N-1+N-2+N-3+...+1=1+2+3+...+N-1=N(N-1)/2
三次循环：N(N+1)/2+(N-1)*N/2+...+2*3/2+1*2/2=N(N+1)(N+2)/6

补充数学公式

1*2/2+2*3/2+3*4/2+……+n(n+1)/2=n(n+1)(n+2)/6
1^2+2^2+3^2+……+n^2=n(n+1)(2n+1)/6
1^3+2^3+3^3+……+n^3=[n(n+1)/2]^2
等比数列求和公式
Sn=a1(q^n-1)/(q-1) （q不等于1）
等差数列求和公式
Sn=na1+n(n-1)d/2