算法之时间复杂度简析

前言

    最近准备对算法进行一些系统的总结和学习，不积跬步无以至千里,不积小流无以成江海.此文主要对时间复杂度进行简单梳理和个人总结，本人才疏学浅，有所疏漏在所难免，如有不当和错误之处，欢迎指正

时间复杂度的定义（Time Complexity）

    时间复杂度，用简单地话描述为：为了大概估算程序运算时间的一种概量。那用什么来估算的呢？用简单的程序执行代码的次数，如int a = 3执行一次，一个n此的for循环表示执行n次等等。广义的T（n）表示在一个完全理想状态的计算机中程序所执行的实际指令次数，下面会提到的O（n）大O（Big Oh），Ω(omega)，Θ(Theta) 都是对T（n）的一个大略估算抽象而来，这里先说明一下个人理解的精确度大小为：T(n)>Θ(Theta)>Ω(omega);Θ(Theta)比Ω(omega)更能确定次数范围。而这集中表示方法，都是基于Big-oh(大O表示法)。

大O表示法简析

    O(f(n))就是大O表示法，里面是一个表达式，可以看成是某一算法所需执行时间始终不会超过某一常数倍的f(n)。严格定义为：存在两个正常數c和n0，若n≥n0时T(n)≤cf(n)，则记为T（n） = O（f(n)）。f(n)又可以称为执行时间的成长率(rate of growth)，结合上面可以看出，常用的大O时间复杂度的估算比真实的次数大（毕竟几乎都会有其他时间消耗），

大O表示法的常用计数方法（根据程序对n的大小对程序执行次数估算（大O法）走势进行判断）

1. O(1)或O© 常数时间

   如普通的一行代码

2. O（n） 线性时间

   int count = 1;
   while(count < n){
       count = count + 2;
       //其他时间复杂度为O(1)的代码 
       //如果使用常数时间只是把问题减少一个常数（如将问题减少1），那么这种算法就是 O(N)
   }
   

   执行n次，线性增长，一个n次的for循环也是O（n）

3. O(log2n) 次线性时间 如：

   int count = 1;
   while(count < n){
       count = count * 2;
   //其他时间复杂度为O(1)的代码 
   }
   //如果一个算法用常数时间(O(1)将问题的大小削减为其一部分（通常是1/2），那么该算法就是 O(log N)
   

   比线性时间增长慢，所以叫次线性时间，二分法的时间复杂度也是O（log2n）。

4. O(n2) 平方时间 如两层循环n次的for循环

5. O(2^n) 指数时间

6. O(n1og2n) 其他多项式时间 注：常见的算法时间复杂度由小到大依次为(n较大时)：O(1)(log2n)(n)(n log2 n)(n^2)(n^3)(2^n)

Ω(omega)表示法定义

    Ω(g(n))也是类似大O法的时间渐进表示法，先说下严格定义：存在两个正常數c和n0，若n≥n0时T(n)≥cf(n)，则记为T（n）= Ω(g(n));和大O表示法进行对比得出，Ω表示法渐进的时间复杂度比真实的小。

Θ(Theta)表示法定义

    Θ(Theta)表示法比上面两种都要精确，第一种严格定义为：当且仅当T（n） = O(h(n)),T(n) = Ω(h(n))，则T（n）=Θ(h(n))，这里理解为此时的渐进时间复杂度的两种算法重叠，前两中表示法和T（n）相等，则此时的h(n)就是T（n）=Θ(h(n))。

++下面引用下个人觉得对Θ(Theta)的不错的定义和理解,引用自market.cloud++

定义：f(n)=Θ(g(n))，若且唯若存在大于0的常數c1,c2和n0，使得对所有n值而言，n≧n0时，c1g(n)≦f(n)≦c2g(n)均成立。事实上f(n)=Θ(g(n))，就是g(n)可同时代表f(n)的上限和下限。以3n+2的例子说明

• 当n≧2时，3n+2≦4n即3n+2=O(n)
• 当n≧l时，3n+2≧3n即3n+2=Ω(n)
• 则我们就可以做成以下的结论3n+2=Θ(n)。

补充（引用自数据结构和算法分析第二版）

    如果用传统的不等式来计算增长率，那么大O法表示T(n)的增长率小于等于f(n)的增长率， Ω中T(n)的增长率大于等于g(n)的增长率，Θ中T(n)的增长率等于h(n)的增长率

参考

《数据结构和算法分析第二版》