理解算法的时间和空间复杂度

Posted on | In , | |

Abstract：算法分析包括事后统计和事前分析估算。事后统计由于依赖于计算机软硬件环境等因素故不太好。事前分析估算是以估算算法的时间复杂度的方式来衡量算法优劣。时间复杂度T(n) = O(f(n))，计算结果只需关注n的最高次幂的数量级即可。而算法的空间复杂度则是对算法在运行过程中临时占用存储空间大小的量度。

算法分析

  • 证明算法正确性
  • 分析算法时间复杂度：反映算法优劣，通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量

方法

  • 事后统计：依赖于计算机的软硬件环境等因素，易掩盖算法本身的优劣
  • 事前分析估算

事前分析估算

一个用高级语言编写的程序在计算机上运行时所消耗的时间取决于下列因素：

  • 算法采用的策略、方法；
  • 编译产生的代码质量；
  • 问题的输入规模；
  • 机器执行指令的速度。

算法的时间量度

  • WHAT：以基本操作的重复执行次数为算法的时间量度，便于比较同一问题的不同算法
  • WHY：算法由控制结构（顺序、分支、循环）和原操作（固有数据类型的操作）组成，算法时间取决于两者的综合效果

时间复杂度

时间频度T(n)：算法中语句执行次数，n为问题规模

时间复杂度：T(n) = O(f(n)),为算法的时间复杂度

  • f(n)为辅助函数，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于0的常数；该式表示存在一个常数C，使得在当n趋近于正无穷时总有T(n)<=C * f(n)，即T(n)在n趋近于正无穷时最大，与f(n)差不多;

eg.O(2n2+n +1) = O (3n2+n+3) = O (7n2 + n) = O ( n2 ) ，一般都只用O(n2)表示即可。注意到大O符号里隐藏着一个常数C，所以f(n)里一般不加系数，只保留主干。如果把T(n)当做一棵树，那么O(f(n))所表达的就是树干，只关心其中的主干，其他的细枝末节全都抛弃不管。

  • 时间频度不同，时间复杂度有可能相同，如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同，但时间复杂度相同，都为O(n2)。
  • 按数量级递增排列,常见的时间复杂度有：常数阶O(1),对数阶O(log2n),线性阶O(n),线性对数阶O(nlog2n),平方阶O(n2)，立方阶O(n3),…， k次方阶O(nk),指数阶O(2n)。
  • 随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。应尽可能选用多项式阶O(nk)的算法，而不希望用指数阶的算法。
  • 常见的算法时间复杂度由小到大依次为：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)

求解算法时间复杂度的步骤：

  • 找出算法中的基本语句：即最内层循环的循环体
  • 计算基本语句的执行次数的数量级：只要保证基本语句执行次数的函数中的最高次幂正确即可，其他细枝末节可忽略
  • 得出O(n)

    btw:1.如果算法中包含嵌套的循环，则基本语句通常是最内层的循环体，如果算法中包含并列的循环，则将并列循环的时间复杂度相加。
    2.Ο(1)表示基本语句的执行次数是一个常数

计算时间复杂度的简单程序分析方法

  • 简单I/O语句或赋值语句：O(1)

  • 顺序结构：求和法则；

    若T1(m)=O(f(m)), T2(n)=O(g(n)),则 T1(m)+T2(n)=O(f(m) + g(n))

  • 选择结构：时间主要耗费在then/else语句上，以及检验条件也需要O(1)时间

  • 循环结构：乘法法则；运行时间主要体现在多次迭代中执行循环体以及检验循环条件的时间耗费

    若算法的2个部分时间复杂度分别为 T1(n)=O(f(n))和 T2(n)=O(g(n)),则 T1T2=O(f(n)g(n)).

  • 复杂算法:可以将它分成几个容易估算的部分,然后利用求和法则和乘法法则计算整个算法的时间复杂度

1.O(n^2) 

1
2
3
4
5
sum=0；                 （一次）        
for(i=1;i<=n;i++)     （n+1次）         
   for(j=1;j<=n;j++) （n2次）       
    sum++；            （n2次）             
//Θ(2n2+n+1)=n^2;只保留主干得：T(n)= =O(n^2)

算法的空间复杂度Space Complexity

定义：对算法在运行过程中临时占用存储空间大小的量度，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。

算法在运行过程中临时占用的存储空间随算法的不同而异，有的算法只需要占用少量的临时工作单元，而且不随问题规模的大小而改变

举例：

  • 当算法的空间复杂度为常量，即不随被处理数据量n的大小而改变时，可表示为O(1)；
  • 当一个算法的空间复杂度与以2为底的n的对数成正比时，可表示为0(10g2n)；当算法的空间复杂度与n成线性比例关系时，可表示为0(n).
  • 若形参为数组，则只需要为它分配一个存储由实参传送来的一个地址指针的空间，即一个机器字长空间；
  • 若形参为引用方式，则也只需要为其分配存储一个地址的空间，用它来存储对应实参变量的地址，以便由系统自动引用实参变量
Thanks!