参考链接
http://blog.sina.com.cn/s/blog_6b7c77e00101hq1z.html
最基本的可以先通过观察来猜测算法时间
1.控制输入量N，对输入量N和时间进行预测，自然界大部分都符合次幂法则，或者支持其他数学模型。
举一个代码例子
public static void countThreeZero(int[]a){ int n = a.length; int count = 0; for(int x=0;x 上面的代码，其中可以看到，if的执行语句次数为 N（N-1）（N-2）=N^3 /6-N^2/2+N/3，当N比较大的时候，可以近视成N^3 /6 即增长数量级 O（N^3）。
分析程序时间所需步骤如下
1.确定输入模型，定义问题的规模。
2.识别内循环
3.根据内循环的操作决定成本模型
4.对于给定输入，判断操作的执行频率，需要一定的数学分析。
比如二分查找，它的输入模型为大小为N的数组a，内循环是一个while循环所有语句，成本模型是比较操作，比较次数最多为lgN+1.
数量级详解
注意：“O”表示量级 (order)，比如说“二分检索是 O(logn)的”,也就是说它需要“通过logn量级的步骤去检索一个规模为n的数组”记法 O ( f(n) )表示当 n增大时，运行时间至多将以正比于 f(n)的速度增长。
这种渐进估计对算法的理论分析和大致比较是非常有价值的，但在实践中细节也可能造成差异。例如，一个低附加代价的O(n2)算法在n较小的情况下可能比一个高附加代价的 O(nlogn)算法运行得更快。当然，随着n足够大以后，具有较慢上升函数的算法必然工作得更快。
O(1)
Temp=i;i=j;j=temp;
分析：
以上三条单个语句的频度均为1，该程序段的执行时间是一个与问题规模n无关的常数。
算法的时间复杂度为常数阶，记作T(n)=O(1)。
这里的1不是1，只是表示一个常数；
如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。
O(n2)
2.1. 交换i和j的内容
sum=0； （一次）
for(i=1;i<=n;i++) （n次 ）
for(j=1;j<=n;j++) （n2次 ）
sum++； （n2次 ）
解：T(n)=2*n2+n+1 =O(n2)
2.2.
for (i=1;i<n;i++)（n-1次）
{
y=y+1; //1
for (j=0;j<=(2*n);j++)（2*n+1次）
x++; //2
}
解： 语句1的频度是n-1
语句2的频度是(n-1)*(2*n+1)=2*n2-n-1
f(n)=2*n2-n-1+(n-1)=2*n2-2
该程序的时间复杂度T(n)=O(n2).
O(n)
2.3.
a=0;
b=1; //1
for (i=1;i<=n;i++) //2
{
s=a+b; //3
b=a; //4
a=s; //5
}
解： 语句1的频度：2,
语句2的频度： n,
语句3的频度： n-1,
语句4的频度：n-1,
语句5的频度：n-1,
T(n)=2+n+3(n-1)=4n-1=O(n).
O(log2n )
2.4.
i=1; //1
while (i<=n)
i=i*2; //2
解： 语句1的频度是1,
设语句2的频度是f(n), 则：2f(n)<=n; f(n)<=log2n
取最大值f(n)= log2n,
T(n)=O(log2n )
O(n3)
2.5.
for(i=0;i<n;i++)
{
for(j=0;j<i;j++)
{
for(k=0;k<j;k++)
x=x+2;
}
}
解： 当i=m, j=k的时候,内层循环的次数为k当i=m时, j 可以取 0,1,...,m-1 ,所以这里最内循环共进行了0+1+...+m-1=(m-1)m/2次
所以,i从0取到n, 则循环共进行了:
0+(1-1)*1/2+...+(n-1)n/2=n(n+1)(n-1)/6所以时间复杂度为O(n3).
我们还应该区分 算法的最坏情况的行为和期望行为。如快速排序的最坏情况运行时间是 O(n2)，但期望时间是 O(nlogn)。通过每次都仔细地选择基准值，我们有可能把平方情况 (即O(n2)情况)的概率减小到几乎等于 0。在实际中，精心实现的快速排序一般都能以 (O(nlogn)时间运行。
下面是一些常用的记法：
访问数组中的元素是常数时间操作，或说O(1)操作。一个算法 如 果能在每个步骤去掉一半数据元素，如二分检索，通常它就取 O(logn)时间。用strcmp比较两个具有n个字符的串需要O(n)时间。常规的矩阵乘算法是O(n3)，因为算出每个元素都需要将n对元素相乘并加到一起，所有元素的个数是n2。
指数时间算法通常来源于需要 求出所有可能结果。例如，n个元素的集合共有2n个子集,所以要求出所有子集的算法将是O(2n)的。指数算法一般说来是太复杂了，除非n的值非常小，因为，在 这个问题中增加一个元素就导致运行时间加倍。不幸的是，确实有许多问题 (如著名的“巡回售货员问题” )，到目前为止找到的算法都是指数的。如果我们真的遇到这种情况，通常应该用寻找近似最佳结果的算法替代之。
技巧1：
For(i=1; i<n; i*=2)
{
}
那么这个程序片段的时间复杂度就是：O(log2n);
在计算程序时间的时候有上界和下界，即算法最好情况和最差情况，下界需要一定的数学功底来讨论，在经典算法中后面会解释，现在先不考虑。
倍率实验
在设计完一个算法的时候，可以根据分析的程序时间进行倍率测试，看看和预期差多少，如下。
package AlthmeticAnalyze;public class RandomArray { public static int[] getRandom(int min,int max,int number){ int n = max-min; int []a = new int [number]; for(int x=0;x 修改其中的RandomArray.getRandom的第三项N值，当输入的N为500时，程序时间大概为15ms，当N为100时大约为110，近似O（n^3）的增长级，因为实际时间考虑很多因素所以测量有时候并不精确。
算法的分析大致为时间复杂度和空间复杂度，空间复杂度的分析首先要明白内存关系。这里学习java内存分配。
byte 1个字节
boolean 1个字节
short 2个字节
char 2个字节
int 4个字节
float 4个字节
long 8个字节
double 8个字节
64位和32位的机器java的内存分配不一样，还可以开启内存压缩这种方法，这里讨论64位无压缩的方法。详情算法分析第四版P126
（分配原则，填充为8的倍数）
1.对象
一个对象的开销是本身16字节和对象里面的数值。比如一个Integer是24字节， 16 是对象字节，4个是存储的int字节，剩下4个填充为8的倍数。
2.链表
比如上一章之前的node链表，多了两个引用字节，一个引用8字节，还有额外开销8，所以一个Node链表是16对象+2*8引用+8额外=40字节。
3.数组
数组在java里面被实现为一个对象，那么一个对象，但是会多4字节记录长度，再填充4字节，则为16+8=24字节+本身存储的大小
如果储存的是对象，因为数组储存的是对象引用，所以需要加一个8字节的引用和对象本身大小。
比如，如果一个Data数组n，大小为 24 + n（8+32） 8为引用大小，32是内存大小。
4.字符串对象
在一个字符串对象里面还有三个int，分别记录偏移量，长度，散列值。
所以一个字符串对象大小为 16+4*3 +指向字符组的引用+填充4字节 = 40字节。
5.字符串值和子字符串
字符串值大小为 40字符串对象+24+2N字节 后面24 + 2N 就是字符数组的大小
子字符串他使用偏移量等计算，所以子字符串就是原来的字符串40大小足够表示