Question

例 x=1; for (i=1;i<=n;i++) for (j=1;j<=i;j++) for (k=1;k<=j;k++) x++;

T(n)=[n(n+1)(2n+1)/6+n(n+1)/2]/2
这个时间复杂度是怎么算的，要详细过程，谢谢！

Answer 1

语句2 for (j=1;j<=i;j++)

语句3 for (k=1;k<=j;k++) x++

第一次： 语句3 执行1次 因为语句2已经满足条件跳出循环（j=1;i=1)

第二次： 语句3执行1+2次 因为语句2 （j=1;i=2)

第三次： 语句3执行1+2+3次 

所以T（n）=1+（1+2）+（1+2+3）+（1+2+3……+n)

=n+2(n-1)+3(n-2)+n(n-(n-1))

=n+2n+3n+n*n -2-6--n(n-1)

=n(n+1)*n/2-(1*1+2*2+3*3+n*n-(1+n)n/2)

=n(n+1)*n/2-(n(n+1)(2n+1)/6-(1+n)n/2)

化简最后为

T（n)=n*(n+1)*(n+2)/6; 化开来就是

T(n)=[n(n+1)(2n+1)/6+n(n+1)/2]/2

形式：

把相等的式子（或字母表示的数）通过“=”连接起来。

等式分为含有未知数的等式和不含未知数的等式。

例如：

x+1=3——含有未知数的等式；

2+1=3——不含未知数的等式。

需要注意的是，个别含有未知数的等式无解，但仍是等式，例如：x+1=x——x无解。

Answer 2

这个从最里层循环开始计算：

最内层是 k=1-j

然后是    j=1-i

然后是   i=1-n；

这样有等式 T(N)为图片所示，然后就是数学计算了。

Answer 3

语句2 for (j=1;j<=i;j++)
语句3 for (k=1;k<=j;k++) x++；
第一次： 语句3 执行1次 因为语句2已经满足条件跳出循环（j=1;i=1)
第二次： 语句3执行1+2次 因为语句2 （j=1;i=2)
第三次： 语句3执行1+2+3次 。。。。。。。
第n次： 语句3执行1+2+3……+n ..........
所以T（n）=1+（1+2）+（1+2+3）……+（1+2+3……+n)
=n+2(n-1)+3(n-2)……+n(n-(n-1))
=n+2n+3n……+n*n -2-6- ……-n(n-1)
=n(n+1)*n/2-(1*1+2*2+3*3……+n*n-(1+n)n/2)
=n(n+1)*n/2-(n(n+1)(2n+1)/6-(1+n)n/2)
化简最后为
T（n)=n*(n+1)*(n+2)/6; 化开来就是
T(n)=[n(n+1)(2n+1)/6+n(n+1)/2]/2

Answer 4

这个从最里层循环开始计算：
最内层是 k=1-j
然后是 j=1-i
然后是 i=1-n；
这样有等式 T(N)为图片所示，然后就是数学计算了。 语句2 for (j=1;j<=i;j++)
语句3 for (k=1;k<=j;k++) x++；
第一次： 语句3 执行1次 因为语句2已经满足条件跳出循环（j=1;i=1)
第二次： 语句3执行1+2次 因为语句2 （j=1;i=2)
第三次： 语句3执行1+2+3次 。。。。。。。
第n次： 语句3执行1+2+3……+n ..........
所以T（n）=1+（1+2）+（1+2+3）……+（1+2+3……+n)
=n+2(n-1)+3(n-2)……+n(n-(n-1))
=n+2n+3n……+n*n -2-6- ……-n(n-1)
=n(n+1)*n/2-(1*1+2*2+3*3……+n*n-(1+n)n/2)
=n(n+1)*n/2-(n(n+1)(2n+1)/6-(1+n)n/2)
化简最后为
T（n)=n*(n+1)*(n+2)/6; 化开来就是
T(n)=[n(n+1)(2n+1)/6+n(n+1)/2]/2

Answer 5

当n=1时，复杂度是1；当n=2时，复杂度是（1+（1+2））；当n=3时，复杂度是（1+（1+2）+（1+2+3））；找到通项an=S(n(1+n)/2),注意an中n为下标，S为求和，根据平方求和公式和等差数列公式可以得到an=[n(n+1)(2n+1)/6+n(n+1)/2]/2，也就是Tn