for(int i = 0; i < n; i++)
for(int j = 0; j < i; j++)
for(int k = 0; k < j; k++)
... 语句 ...
0 + 1 + 2 + 3 + ... + n-2 + n-1 = n(n-1)/2
i : 0 1 2 3
j : 0 0 1(跳) 0 1 2(跳) 0 1 2 3(跳)
count: 0 0 0+1 0+1+2 0+1+2+3 0+1+2+3+4 ... 0 1 2 3 4...(n-3) 0 1 2 3 4 ... (n-2)
(n-n)(n-(n+1))/2 + (n-(n-1))(n-n)/2 + (n-(n-2))(n-(n-1))/2 + ..................................... + (n-2)(n-3)/2 + (n-1)(n-2)/2
1
1 2
1 2 3
1 2 3 4
1 2 3 4 5
1 2 3 4 5 6
.
.
.
1 2 3 4 5 6 ... n-2
1 2 3 4 5 6 ... n-2 n-1
1 2 3 4 5 6 ... n-2 n-1 n
{--------------------------------n/2--------------------------------}
n + 2(n-1) + 3(n-2) + 4(n-3) + 5(n- 4) + 6(n-5) + ... + (n/2)*(n/2+1) {if (n = 2k)}
{--------------------------------(n+1)/2----------------------------------}
n + 2(n-1) + 3(n-2) + 4(n-3) + 5(n- 4) + 6(n-5) + ... + ((n+1)/2)*((n+1)/2) {if (n = 2k+1)}
1*1+2*2+3*3+...+(n-1)(n-1)+n*n 2n+1
1 5 5 1+5+5
2 2 5 4 4 5 2+5+4 2+4+5
3 3 3 5 4 3 3 4 5 3+5+3 3+4+4 3+3+5
4 4 4 4 5 4 3 2 2 3 4 5 4+5+2 4+4+3 4+3+4 4+2+5
5 5 5 5 5 5 4 3 2 1 1 2 3 4 5 5+5+1 5+4+2 5+3+3 5+2+4 5+1+5
r r r (n*(n+1)/2)*(2n+1)
3r = n(n+1)(2n+1)/2 --> r = n(n+1)(2n+1)/6
n+2(n-1)+3(n-2)+...+(n-1)2+n*1 n+2
5 1 1 5+1+1
4 4 1 2 2 1 4+1+2 4+2+1
3 3 3 1 2 3 3 2 1 3+1+3 3+2+2 3+3+1
2 2 2 2 1 2 3 4 4 3 2 1 2+1+4 2+2+3 2+3+2 2+4+1
1 1 1 1 1 1 2 3 4 5 5 4 3 2 1 1+1+5 1+2+4 1+3+3 1+4+2 1+5+1
r r r (n*(n+1)/2)*(n+2)
3r = n(n+1)(n+2)/2 --> r = n(n+1)(n+2)/6
T(n) = (n-2)(n-1)n/6 = O(n^3)
颇为神奇的方法:可将数值排列为想象的正三角形,设一个正三角内的所有值的和为 r。旋转两次(每次顺时针或逆时针旋转120度,这里是顺时针旋转)使此正三角的每个角都竖直向上。依次将这样排列好的正三角内的所有对应位置的值相加,而后得到的每个位置的值将相等,且等于一个关于 n 的函数的值。最终发现等差数列之和个相同的关于 n 的函数的值,十分便于计算。