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 时间复杂度的计算步骤

1. 计算出基本操作的执行次数T(n)
     基本操作即算法中的每条语句（以;号作为分割），语句的执行次数也叫做语句的频度。在做算法分析时，一般默认为考虑最坏的情况。

2. 计算出T(n)的数量级
     求T(n)的数量级，只要将T(n)进行如下一些操作：忽略常量、低次幂和最高次幂的系数。令f(n)=T(n)的数量级。

3. 用大O来表示时间复杂度
     当n趋近于无穷大时，如果lim(T(n)/f(n))的值为不等于0的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))。

总结一下就是

1. 找到执行次数最多的语句
2. 计算语句执行次数的数量级
3. 用大O来表示结果

0x03 例子

1. 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)。

2. O(n)

int sum = 0;
for(int i = 0; i < n; i++){
    sum = sum + i;
}

T(n) = 1 + n
上述代码的时间复杂度就是for循环的O(n)

3. 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)

4. 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