目录：
1.如何评价算法性能？
2.大O表示法
3.常见时间复杂度大小及其比较
4.一些较为复杂的实例
如何评价算法性能？
数据结构和算法，本质上是解决现实存在的问题，即如何让解决指定问题的代码运行得更快？一个算法如果能在所要求的资源限制(resource constraint)内将问题解决好，则称这个算法是有效率的(effient)。
限制可分为空间限制和时间限制。
而算法的速度，算法需求多少空间如何衡量呢？
你可能会说，我可以通过如下代码来测试代码的运行时间：
//JAVA CODE
void calcDuration(){
long begin = System.currentTimeMillis();
function(n);
long end = System.currentTimeMillis();
}
我们可以通过end-begin来计算出function()的执行时间。这类“事后统计”的方法用来评估算法执行效率是正确的，但是它也有它的局限性：
受不同机器配置的影响，结果差异不同，甚至同一段算法，在不同机器上跑出来的结果差异很大。
算法的测试结果受输入的规模影响很大，也就是说，输入不同规模的数据，结果差别非常大。
能不能事先“算”出算法的执行效率呢？这就引出了以下两个概念：时间复杂度，空间复杂度。
大O表示法
首先看一个简单的例子：
void foo(){
for(int i =0;i<n;i++){//执行了n次
System.out.println("Hello world");//执行了n次
}
System.out.println("function over");//执行了1次
}
在上述例子中，第1行的代码总共执行了n次，第2行的代码总共执行n次，第4行代码会执行1次。
这里假设计算机处理语句代价(如：赋值，自增，输出等)都为c；(当然，可以拟定一个最小单位，让所有语句的代价与c成正比)。
假设算法总执行时间为T(n)，其中n为问题的规模；
那么上述代码的总执行时间：T(n) = (2n +1)c
可以看出，T(n)与代码的总执行次数总是成正比的，即与(2*n+1)成正比；
我们将代码执行次数用f(n)来表示，即f(n) = 2*n+1。
我们算出了代码的执行次数后，如何表示算法的复杂度呢？
在计算机中，我们一般采用大O渐进表示法来表示算法的复杂度。即
T(n) = O(f(n))
将上述f(n)带入，我们得出T(n) = O(n),因此，上述算法的时间复杂度为O(n),细心的同学发现了，f(n)不是等于2*n+1吗？，为什么到里面就没有了呢？
其实大O并不是表示代码真正的执行时间，而是代码执行时间随着数据规模增长的变化趋势。具有以下特点：
1.不保留系数；
2.且只保留最高阶的项。
这里稍微解释下第二条，低阶项在问题规模n慢慢增大的时候，对结果影响慢慢变小，所以在计算时间复杂度的时候，可以省去。可以把大O符号想象成一个过滤形的一个漏斗，过滤那些系数以及低阶的项。
比如:f(n) = 2n^2+5n+1; 则时间复杂度记为O（n^2）
常见算法复杂度大小及其比较
O(1)<O(logn)<O(n)<O(nlogn)<O(n)<O(n^2) <O(2^n)<O(n!)
log函数统一以2为底。
以上是算法复杂度大小与比较，需要注意的是除开O(2^n)与O（n!）外其他的被称为多项式时间，这个概念后续会再次提及（NP问题）现在你只需要知道多项式是什么概念就行了。
另外我在初学的时候经常分不清2^n与n!的大小比较
其实你把他展开来看就好了。
2 *2 *2 *2.....(n个2)
1 *2 *3 *4.....(n个数)
这样是不是就清楚了呢？
一些较为复杂的实例
实例1
for(int i =0;i<n;i++){
for(int j = 0;j<m;j++){
System.out.println("sth");/*运行m*n次*/
}
}
在做时间复杂度题目的时候，我们往往只需要注意哪些语句频度最高的语句，比如上例中的第三行，总计会运行m*n次，所以上例的时间复杂度为O(mn)。注意：一般问题规模我们会用n来表示，但是经常会有多个影响问题规模的参数出现，比如上例。
实例2
int i =1;
while(i<=n){
i = i*2;
}
很多初学者看到上面的代码就头大，不知道分析，实际上这道题就是问:
i = i*2会运行多少次? 等价于
1 * 2 * 2 * 2.....*2 = n，有多少个乘2? 等价于
2^k = n，求k
所以k = logn ，所以，时间复杂度为O(logn)
稍微变形下，如果替换成语句i = i*3或者其他的呢？？
我们可以根据上述公式，把任意不以2为低的log函数，换成以2为低，而大O符号又是省略系数的，所以不管是i = i*3，i = i * 4，i = i * 5，...都统一记为O(logn)。
实例3
void foo(int m){
for(int i = 0;i<m;i++)
System.out.println("sth");
}
void koo(int n){
for(int i =0;i<n;i++)
foo(n);//第7行
}
我们要求koo函数的时间复杂度，由于koo函数的内部又调用了foo，所以将koo的内部看成一个双层for循环，所以koo的时间复杂度为O(n^2)。
思考：如果将第7行的调用改成foo(i)呢？
实例4
int Fib(int n){//斐波那契数列
if(n<3) return 1;
else return Fib(n-1)+Fib(n-2);
}
上述实例是求斐波那契数列的递归形式，递归算法的时间复杂度往往更难求得，画出调用过程为下图：
递归算法的复杂度，为这颗二叉树的节点数。
我们知道满二叉树的节点数为2^h -1,其中h为树的高度，那树的高度怎么求呢？
我们可以看红线部分表示这棵树每一层最左边的节点，它的特征很明显，等于n-1（n是输入规模）。所以这个算法的最终复杂度为O(2^n)。
值得一提的是，这是一种非常不好的写法。有很多求斐波那契数列好的算法，暂时就不再赘述了。
