一.算法时间复杂度的定义
进行算法分析时，句子的总执行次数t(n )是关于问题规模n的函数，进而分析n引起的t ) n )的变化，决定t ) n )的顺序。 算法的时间复杂度，即算法的时间尺度。 (t ) n )=o ) f ) n )。 这表明随着问题n的增大，算法运行时间的增长率与f(n )的增长率相同，称为算法的渐进时间复杂度，简称时间复杂度。 这里，f(n )是有问题规模n的函数。
这样，用大写的o ()表示算法的时间复杂性的记法称为big 0记法。
二.导出大o次的方法
1、将运行时间中的所有加法常数替换为常数1。
2、修改后的执行次数函数中，只保留最上位项。
3、存在最上位项且不是1时，去除与该项相乘的常数。 结果，得到了很大的o次。
三.推演范例
1、常数级
首先，顺序结构的时间复杂性。 下一个算法是利用高斯定理计算1，2，……n的个数之和。
1 int sum=0，n=100； /*执行一次*
2
3sum=(1n ) ) n/2； /*执行一次*
4
5printf('%d '，sum )； /*执行一次*
该算法的执行次数函数为f[n]=3。 根据我们推导大0阶的方法，第一步是将常数项3改为1。 如果保留最上位项，则由于没有最上位项，可知该算法的时间复杂度为0(1)。
另外，该算法中的语句sum=(1n ) *n/2； 如果有10个句子的话，例子和给定的代码是3次和12次的不同。 具有这种问题的大小(与n的多寡无关，执行时间一定的算法为o ) )1)的时间复杂性，也称为常数阶。 关于分支结构，无论是真还是假，执行次数都是一定的，不会随着n的增大而变化，因此即使是单纯的分支结构(不包含在循环结构中)，时间复杂度也为0(1)。
2、线性步长
线性阶的循环结构变得相当复杂。 要确定算法的阶数，经常需要确定特定语句或语句集的执行次数。 因此，要分析算法的复杂性，分析循环结构的执行情况是很重要的。
下一代码为循环的时间复杂度为o(n )。 因为循环中的代码需要执行n次。
1 inti； 2
3for(I=0； i n； I({4} )
5 /*时间复杂度为o(1)的手续) /
6
7 }
3、对数层
以下代码：
1 int count=1； 2
3while(count
5 count=count * 2； 6
7 /*时间复杂度为o(1)的手续) /
8
9 }
因为每次在count乘以2之后，都接近了n一分。 也就是说，如果乘以几个2大于n，就会退出循环。 由2^x=n得到x=logn。 因此，该环路的时间复杂度为o(logn )。
4、平方层
下一个例子是循环的嵌套，其内环如刚才分析的那样，时间复杂度为o(n )。
1 inti，j； 2
3for(I=0； i n； I({4} )
5for(j=0； j n； j({6} )
7 /*时间复杂度为o(1)的手续) /
8
(十)十
11 }
对于外层环，内部这一时间复杂度仅为o(n )的语句，进行n次再循环。 因此，此代码的时间复杂度为o(n^2)。
如果将外环的循环次数更改为m，时间复杂度为o(mxn )。
因此，循环的时间复杂度可以概括为循环整体的复杂度乘以该循环被执行的次数。
那么，下一个循环嵌套，时间的复杂性是多少呢？
1 inti，j； 2
3for(I=0； i n； I({4} )
5for(j=I； j n； j((/*注意不是j=i而是0 ) /
6
7 /*时间复杂度为o(1)的手续) /
8
(十)十
11 }
因为i=0时，内循环执行n次，i=1时执行n-1次，i=n-1时执行1次。 所以总执行次数为：
我们导出大o次的方法，第一条，没有加法常数就不考虑； 第二条，只保留最上位项，如果保留(n )2)/2； 去掉第三条、本项乘法的常数，即去掉1/2，最终该码的时间复杂度为o(n2 )。
从这个例子中也可以得到这样的经验，即实际上理解大0的导出并不难。 难的是对数列的一些相关运算，这往往是考察你的数学知识和能力。
5、立方层
以下示例是三重循环嵌套。
1 inti，j； 2
3for(I=
1; i < n; i++)45 for(j = 1; j < n; j++)6
7 for(j = 1; j < n; j++){8
9 /*时间复杂度为O(1)的程序步骤序列*/
10
11
12
13 }
这里循环了(1^2+2^2+3^2+……+n^2) = n(n+1)(2n+1)/6次，按照上述大O阶推导方法，时间复杂度为O(n^3)。
四、常见的时间复杂度
常见的时问复杂度如表所示。
常用的时间复杂度所耗费的时间从小到大依次是：
我们前面已经谈到了。O(1)常数阶、O(logn)对数阶、O(n)线性阶、 O(n^2)平方阶等，像O(n^3)，过大的n都会使得结果变得不现实。同样指数阶O(2^n)和阶乘阶O(n!)等除非是很小的n值，否则哪怕n 只是100，都是噩梦般的运行时间。所以这种不切实际的算法时间复杂度，一般我们都不去讨论。
五、最坏情况与平均情况
我们查找一个有n 个随机数字数组中的某个数字，最好的情况是第一个数字就是，那么算法的时间复杂度为O(1)，但也有可能这个数字就在最后一个位置上待着，那么算法的时间复杂度就是O(n)，这是最坏的一种情况了。
最坏情况运行时间是一种保证，那就是运行时间将不会再坏了。 在应用中，这是一种最重要的需求， 通常， 除非特别指定， 我们提到的运行时间都是最坏情况的运行时间。
而平均运行时间也就是从概率的角度看， 这个数字在每一个位置的可能性是相同的，所以平均的查找时间为n/2次后发现这个目标元素。平均运行时间是所有情况中最有意义的，因为它是期望的运行时间。也就是说，我们运行一段程序代码时，是希望看到平均运行时间的。可现实中，平均运行时间很难通过分析得到，一般都是通过运行一定数量的实验数据后估算出来的。一般在没有特殊说明的情况下，都是指最坏时间复杂度。
六、算法空间复杂度
我们在写代码时，完全可以用空间来换取时间，比如说，要判断某某年是不是闰年，你可能会花一点心思写了一个算法，而且由于是一个算法，也就意味着，每次给一个年份，都是要通过计算得到是否是闰年的结果。 还有另一个办法就是，事先建立一个有2050个元素的数组(年数略比现实多一点)，然后把所有的年份按下标的数字对应，如果是闰年，此数组项的值就是1，如果不是值为0。这样，所谓的判断某一年是否是闰年，就变成了查找这个数组的某一项的值是多少的问题。此时，我们的运算是最小化了，但是硬盘上或者内存中需要存储这2050个0和1。这是通过一笔空间上的开销来换取计算时间的小技巧。到底哪一个好，其实要看你用在什么地方。
算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记作:S(n)= O(f(n))，其中，n为问题的规模，f(n)为语句关于n所占存储空间的函数。
一般情况下，一个程序在机器上执行时，除了需要存储程序本身的指令、常数、变量和输入数据外，还需要存储对数据操作的存储单元，若输入数据所占空间只取决于问题本身，和算法无关，这样只需要分析该算法在实现时所需的辅助单元即可。若算法执行时所需的辅助空间相对于输入数据量而言是个常数，则称此算法为原地工作，空间复杂度为0(1)。
通常， 我们都使用"时间复杂度"来指运行时间的需求，使用"空间复杂度"指空间需求。当不用限定词地使用"复杂度'时，通常都是指时间复杂度。
七、一些计算的规则
1、加法规则
T(n,m) = T1(n) + T2(m) = O(max{f(n), g(m)})
2、乘法规则
T(n,m) = T1(n) * T2(m) = O(max{f(n)*g(m)})
3、一个经验
复杂度与时间效率的关系：
c(常数) < logn < n < n*logn < n^2 < n^3 < 2^n < 3^n < n!
l------------------------------l--------------------------l--------------l
较好 一般 较差
八、常用算法的时间复杂度和空间复杂度
--------------------------------------------
参考：
《大话数据结构》
http://blog.csdn.net/yangwei282367751/article/details/52426911
http://univasity.iteye.com/blog/1164707