1.算法分析概述
算法分析就是分析算法占用计算机资源的多少。计算机资源主要是cpu时间和内存空间，分析算法占用cpu时间的多少称为时间性能分析，分析算法占用内存空间的多少称为空间性能分析。
算法分析的目的是分析算法的时间空间性能以便改进算法
2.计算算法时间复杂度的基本方法
1.找出基本频度最大的那条语句作为基本语句
2.计算基本语句的频度得到问题规模n的某个函数f(n)
3.取其数量级用符号"O"表示
例如：(这里代码并不是完整的代码，只是为了说明求解的方法，写出来重要的几步)
for(i=0;i<=n;i++) for(j=1;j<=i;j+++) for(k=1;k<=j;k++) x=x+1;
语句平度=
=n(n+1)(n+2)/6
n的最高次幂为n的三次方 所以：
T(n)=O(n^{3})
例如：
i=1; //(1) while(i<n) i=i*2 //(2)
(1)若循环执行次数为1次：i=1*2=2
若循环执行次数为2次：i=2*2=2^2
若循环执行次数为3次：i=2^3
若循环执行次数为n次：i=2^x
设语句（2）执行次数为x次
i<=n;
所以2^x=n 即x<=
取最大值f(n)=log
时间复杂度T(n)=O(log) ==>o(lgn)
3.特殊算法的时间复杂度
有的情况下，算法基本操作重复执行的次数还随问题的输入数据集不同而不同
例如：顺序查找，在数组a[i]中查找值等于e的元素，返回其所在位置。
for(i=0;i<n;i++) if(a[i]==e) return i+1; return 0;
最好情况：1次
最坏情况：2次
平均时间复杂度为：O(n)
所以分析时间复杂度为多少一般考虑（1）和（2）
（1）最坏时间复杂度：
指在最坏情况下，算法的时间复杂度。
（2）平均时间复杂度：
指在所以可能输入实列在等概率出现的情况下，算法的期望运行的时间
（3）最好时间复杂度
指在最好情况下，算法的时间复杂度
一般总是考虑在最坏情况下的时间复杂度，以保证算法的运行时间不会更长。
4.难以求出的时间算复杂度
有的算法比较复杂，O(n)很难表示
对于复杂的算法，可以将他分成几个容易估计的部分，然后利用O加法法则和乘法法则，计算算法的时间复杂度：
a）加法法则
T(n)=T1(n)+T2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n))
b)乘法法则
T(n)=T1(n)×T2(n)=O(f(n))×O(g(n))=O((f(n)×g(n))
算法时间效率比较：
当n取得很大时，指数时间算法和多项式时间算法在所需时间非常悬殊
算法时间复杂的由低到高
在设计程序时候应该考虑算法时间复杂度较低的程序
5.渐进空间复杂度
空间复杂度：
算法所需存储空间的度量
记作：s(n)=O(f(n))
其中n为问题的规模（或大小）
算法占据的空间
-->算法本身要占据空间，输入/输出，指令，常数，变量等。
-->算法要使用的辅助空间
eg：将一堆数组a中的几个数逆序存放到原数组中：
算法1:
for(i=0;i<n/2;i++) { t=a[i]; a[i]=a[n-i-1]; a[n-i-1]=t; }
算法2：
for(i=o;i<n;i++) { b[i]=a[n-i-1]; } for(i=0;i<n;i++) { a[i]=b[i]; }
算法1的时间复杂度S(n)=O(1) 常数阶
算法2的时间复杂度S(n)=O(n) 一次阶
所以算法1比算法2更好
