0x01 时间复杂度的定义
算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))，称O(f(n))为算法的渐进时间复杂度(O是数量级的符号 )，简称时间复杂度。
0x02 时间复杂度的计算步骤
计算出基本操作的执行次数T(n)
基本操作即算法中的每条语句（以;号作为分割），语句的执行次数也叫做语句的频度。在做算法分析时，一般默认为考虑最坏的情况。计算出T(n)的数量级
求T(n)的数量级，只要将T(n)进行如下一些操作：忽略常量、低次幂和最高次幂的系数。令f(n)=T(n)的数量级。用大O来表示时间复杂度
当n趋近于无穷大时，如果lim(T(n)/f(n))的值为不等于0的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))。
总结一下就是
- 找到执行次数最多的语句
- 计算语句执行次数的数量级
- 用大O来表示结果
0x03 例子
- O(1)
int i = 0,j = 0,temp = 0;
temp = i;
i = j;
j = temp;
这个是一个交换两个变量值的例子，三个语句的频度都是1，该程序执行时间是一个与问题规模n无关的，算法的时间复杂度为常数，所以T(n) = O(1)。
P.S 如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。
- O(n)
int sum = 0;
for(int i = 0; i < n; i++){
sum = sum + i;
}
T(n) = 1 + n
上述代码的时间复杂度就是for循环的O(n)
- O(logn)
int i= 1;
while(i<n){
i = i*2;
}
设i=i*2的频度为t，则2^t <= n，那么t <= log2n。取最坏结果，当t等于最大值log2n是T(n) = 1 + log2n，所以时间复杂度为O(log2n)
- O(n^2)
int sum = 0;
for(int i = 0;i <= n;i++){
for(int j = 0;j <= n; j++){
sum++;
}
}
时间复杂度为O(n^2)
0x04 常用排序算法的时间复杂度
常见排序算法时间复杂度
0x05 参考文献
http://www.jianshu.com/p/99bac69fdd97
http://univasity.iteye.com/blog/1164707
http://blog.csdn.net/zolalad/article/details/11848739
