algs里分析ThreeSum算法的执行时间时用到了三层循环的执行次数，文章里只给了结论没有计算过程。不知道原理，只知道结果，不符合我的学习习惯，所以我用自己的方法尝试计算。下面是示例代码：
 
for (int i = 0; i < N; ++i) {
	for (int j = i + 1; j < N; ++j) {
		for (int k = j + 1 ; k < N; ++k) {
			// do something
		}
	}
} 
 
显而易见，最外层的循环的执行次数是$N$次，第二层循环次数是个等差数列：$N-1,N-2,N-3,...,3,2,1,0$，所以第二层循环的执行次数是$\frac{N(N-1)}{2}$。第三层循环次数就不是那么直观了，可以先把i和j的值带入具体的值来分别计算第三层的循环次数，然后再分析下规律。
 
当$i=0,j\in [1,N-1]$时
 
i
j
第三层的循环次数
0
1
N-2
0
2
N-3
0
3
N-4
0
N-3
2
0
N-2
1
0
N-1
0
当$i=1,j\in [2,N-1]$时
 
i
j
第三层的循环次数
1
2
N-3
1
3
N-4
1
4
N-5
1
N-3
2
1
N-2
1
1
N-1
0
当$i=2,j\in [3,N-1]$时
 
i
j
第三层的循环次数
2
3
N-4
2
4
N-5
2
5
N-6
2
N-3
2
2
N-2
1
2
N-1
0
当$i=N-4,j\in [N-3,N-1]$时
 
i
j
第三层的循环次数
N-4
N-3
2
N-4
N-2
1
N-4
N-1
0
当$i=N-3,j\in [N-2,N-1]$时
 
i
j
第三层的循环次数
N-3
N-2
1
N-3
N-1
0
当$i=N-2,j\in [N-1,N-1]$时
 
i
j
第三层的循环次数
N-2
N-1
0
可以得出第三层循环的循环次数是与i相关的等差数列。
 
i
第三层的循环次数等差数列
第三层循环的循环次数和
0
N-2, N-3, N-4, N-5, N-6, N-7, …, 2, 1, 0
$\frac{(N-2)(N-1)}{2}$
1
N-3, N-4, N-5, N-6, N-7, …, 2, 1, 0
$\frac{(N-3)(N-2)}{2}$
2
N-4, N-5, N-6, N-7, …, 2, 1, 0
$\frac{(N-4)(N-3)}{2}$
…
…
…
N-4
2, 1, 0
3
N-3
1, 0
1
N-2
0
0
由等差数列求和公式$f(n)=\frac{n^2+n}{2}$可得第三层循环的循环次数和$sum(i)=\frac{(N-2-i{)}^2+(N-2-i)}{2},i\in [0,N-2]$，于是第三层循环的循环次数总和$\sum _{i=0}^{N-2}sum(i)$
 $=\sum _{i=0}^{N-2}\frac{(N-2-i{)}^2+(N-2-i)}{2}$
 $=\frac{(N-2{)}^2+(N-2)}{2}+\frac{(N-3{)}^2+(N-3)}{2}+\frac{(N-4{)}^2+(N-4)}{2}+...+\frac{(2{)}^2+(2)}{2}+\frac{(1{)}^2+(1)}{2}+\frac{(0{)}^2+(0)}{2}$
 $=\frac{(N-2{)}^2+(N-3{)}^2+(N-4{)}^2+...+(2{)}^2+(1{)}^2+(0{)}^2+(N-2)+(N-3)+(N-4)+...+2+1+0}{2}$
 
平方和公式$\sum _{k=1}^n{k}^2=\frac{n(n+1)(2n+1)}{6}$和等差数列求和公式$f(n)=\frac{n^2+n}{2}$，所以
 $\frac{(N-2{)}^2+(N-3{)}^2+(N-4{)}^2+...+(2{)}^2+(1{)}^2+(0{)}^2+(N-2)+(N-3)+(N-4)+...+2+1+0}{2}$
 $=\frac{\frac{(N-2)(N-2+1)(2(N-2)+1)}{6}+\frac{(N-2{)}^2+(N-2)}{2}}{2}$
 为了方便计算，代入N-2=a
 $\frac{\frac{(N-2)(N-2+1)(2(N-2)+1)}{6}+\frac{(N-2{)}^2+(N-2)}{2}}{2}$
 $=\frac{\frac{a(a+1)(2a+1)}{6}+\frac{a^2+a}{2}}{2}$
 $=\frac{\frac{a(a+1)(2a+1)+3a(a+1)}{6}}{2}$
 $=\frac{\frac{(a+1)(2a^2+a+3a)}{6}}{2}$
 $=\frac{a(a+1)(a+2)}{6}$
 再代入a=N-2
 $=\frac{a(a+1)(a+2)}{6}$
 $=\frac{(N-2)(N-1)N}{6}$
 所以
 第三层循环的循环次数总和$\sum _{i=0}^{N-2}sum(i)=\frac{(N-2)(N-1)N}{6}$

N=INT（（终值-初值）/步长）+1 

示例代码展示
 
1.for(i=1;i<=n;i++){										//n+1次
2. 	for(j=1;j<=n;j++){									//n(n+1)次
3. 		c[i][j]=0;											//n*n次
4.		for(k=0;k<n;k++)								//n*n*(n+1)次
5.			c[i][[j]=c[i][[j]+a[i][j]*b[k][j];			//n*n*n次
6.	}
7.}
 
示例代码为两个n × n矩阵相乘的算法
 
我们把算法所耗费的时间定义为该算法每条语句的频度之和：
 T(n)=2n3 +3n2 2n+1
 
算法的时间复杂度例题
 

 1. i=1;
 2. while(i<=n)
 3. 	i=i*2;

 

 
 
若循环执行一次：i=1*2=2，
若循环执行一次：i=2*2=22,
若循环执行一次：i=2*2=23,
若循环执行X次：i=2x
 设语句 i+i*2 执行次数为x次，
 由循环条件i<=n，所以2x <=n，所以 x<=log2 n
 
2f(n) <=n，即f(n)<=log2 n，取最大值，f(n) = log2 n，
 所以该程序段的时间复杂度T(n)=O(log2 n)。

package test;

public class Fortest {

	public static void main(String[] args) {
	    int x=0;
	    int n=3;
		
		for (int i=1;i<=n;i++){
			for(int j=1;j<=i;j++){
				for(int k=1;k<=j;k++){
					x++;
					System.out.println(x);
				}
			}
		  } 		
	}

}
 
我们来看以上程序，如果只计算时间复杂度，可以看出来，预估时间复杂度为n^3
 
不过要计算x的值，即循环次数。就会稍微麻烦。很容易绕晕。
 
一般性公式：(n(n+1)(n+2)(n+4)...)/(1*2*3*4...)