算法复杂度分析 - liuyangfei的博客

时间复杂度

时间频度

一个算法中的语句执行次数称为时间频度，记作$T(n)$。

时间复杂度

在时间频度中，n称为问题的规模，当n不断变化时，时间频度$T(n)$也会不断变化。时间复杂度是用来衡量时间频度变化规律。一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用$T(n)$表示，若某个辅助函数$f(n)$使得当n趋近于无穷大时，$\frac{T(n)}{f(n)}$的极限值为不等于0的常数，则称$f(n)$是$T(n)$的同数量级函数。记作$T(n)=O(f(n))$，称$O(f(n))$为算法的渐近时间复杂度。

求解时间复杂度的具体步骤

找出算法中的基本语句；

算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。
计算基本语句的执行次数的数量级；

只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率。
用$O$记号表示算法的时间性能。

$O(1)$表示基

本语句的执行次数是一个常数，一般来说，只要算法中不存在循环语句，其时间复杂度就是$O(1)$。其中$O(\log_2n)、O(n)、O(n\log_2n)、O(n^2)、O(n^3)$称为多项式时间，而$O(2^n)、O(n!)$称为指数时间。计算机科学家认为多项式时间复杂度的算法是有效算法，称为P(Polynomial)类问题，而指数时间复杂度的算法称为NP(Non-Deterministic Polynomial)问题。

在计算算法时间复杂度时有以下几个简单的程序分析法则

对于一些简单的输入输出语句或赋值语句,近似认为需要$O(1)$时间
对于顺序结构,需要依次执行一系列语句所用的时间可采用大O下”求和法则”

求和法则：是指若算法的2个部分时间复杂度分别为$T_1(n)=O(f(n))$和 $T_2(n)=O(g(n))$,则$T_1(n)+T_2(n)=O(max(f(n), g(n)))$，若$T_1(m)=O(f(m)), T_2(n)=O(g(n))$，则$T_1(m)+T_2(n)=O(f(m) + g(n))$。

对于选择结构,如if语句,它的主要时间耗费是在执行then字句或else字句所用的时间,需注意的是检验条件也需要$O(1)$时间
对于循环结构,循环语句的运行时间主要体现在多次迭代中执行循环体以及检验循环条件的时间耗费,一般可用大O下”乘法法则”

乘法法则: 是指若算法的2个部分时间复杂度分别为$T_1(n)=O(f(n))$和$T_2(n)=O(g(n))$，则$T_1T_2=O(f(n)g(n))$

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

分别对几个常见的时间复杂度进行示例说明

$O(1)$

 Temp=i; i=j; j=temp;                

$O(n^2)$

sum=0；                 #（一次）
for(i=1;i<=n;i++)     #（n+1次）
   for(j=1;j<=n;j++) #（n2次）
       sum++；        #    （n2次）

$O(log_2n)$

i=1;     #①
while (i<=n)
    i=i*2;# ②

空间复杂度

一个算法的空间复杂度定义为该算法所耗费的存储空间，也是问题规模n的函数。

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法的输入输出数据所占用的存储空间是由要解决的问题决定的，是通过参数表由调用函数传递而来的，它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比，要压缩这方面的存储空间，就必须编写出较短的算法。算法在运行过程中临时占用的存储空间随算法的不同而异，有的算法只需要占用少量的临时工作单元，而且不随问题规模的大小而改变，我们称这种算法是“就地"进行的，是节省存储的算法；有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元。

时间复杂度

空间复杂度

FEATURED TAGS