Chapter2: 时间复杂度分析、递归、查找与排序

5. 算法时间复杂度评估

大O表示法评估算法复杂度

什么是大O表示法

所谓的时间复杂度，实际上就是一个输入规模 n与函数运行时间f(n) 的关系，比如 O(n^2) 就表示当处理100个输入时，要进行10000次访问/计算操作, 再乘以单次运算需要的单位时间即得到算法运行时间。

大O表示法，忽略常数项、低阶项等非主体部分，如 f(n)=2n^2=n+5 的时间复杂度为O(n^2)， 对于 O() 里面的内容，如这里的 n^2 ,存在一个常数使得函数的运行时间 f(n) 趋近并小于 c*n^2 ,这个 n^2 成为这个算法的渐进上界。

大O表示法评估算法时间复杂度距离

• O(n)

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

• O(n^2)

  • example1

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

  • example2

    下面算法中，内层循环的限制条件是 i<j ，相当于总执行次数为1+2+3+...n=(1+n)n/2, 时间复杂度仍为O(n^2)

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

• O(log(n))

  注意 count 的增长是指数级的，设执行次数为 k, 则2^k=n, k=log(n) ,即时间复杂度为O(log(n))

  int count=1;
  while(count<n){
      count=count*2;
  }
  

常见函数复杂度计算

现代计算机的处理速度大概是1s处理10^8的数据，由此我们可以推算出下表：
计算方法，问题规模是自变量，时间复杂度是函数，将问题规模代入时间复杂度公式，再除以10^8 即得到所耗费的时间。而问题规模实际上就是执行的语句数

时间复杂度	所耗费的时间	问题规模
O(logn)	27/10^8	10^8
O(n)	1	10^8
O(n^2)	10^8	10^8
O(n^3)	10^16	10^8
O(2^n)	2(108)	10^8

怎样的时间复杂度才算合格的算法

常见的时间复杂度评价

参考资料

[1] 常见函数时间复杂度