计算与计算思维：算法复杂度解析

算法复杂度分为时间复杂度和空间复杂度。其作用：时间复杂度是指执行算法所需要的计算工作量；而空间复杂度是指执行这个算法所需要的内存空间。

1.时间复杂度

算法的时间复杂度反映了算法执行的时间长短，它是度量一个算法好坏的重要指标。

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T（n）表示，若有某个辅助函数f（n），使得当n趋近于无穷大时，T（n）/f（n）的极限值为不等于零的常数，则称f（n）是T（n）的同数量级函数。记作T（n）=O（f（n）），称O（f（n））为算法的渐进时间复杂度，简称时间复杂度。

度量一个算法的时间复杂度通常有两种方式：

·事后统计法

·事前分析法（大O表示法）

算法的时间复杂度是由最深层嵌套语句的频度决定的。

大O表示法的推导：

1.用常数1取代运行时间中的所有加法常数

2.在修改后的运行次数函数中，只保留最高阶

3.将最高阶系数变为1

例1：

所以其时间复杂度为O（n2）。(www.xing528.com)

例2：

执行的总次数满足：

所以它的时间复杂度为O（logn）

例3：分析冒泡排序算法的时间复杂度

最佳情况下（初始状态是正序时），冒泡排序算法只需要一次扫描即可完成排序，此时比较次数Cmin=n·1，移动次数Mmin=0，所以时间复杂度为O（n）

最差情况下（初始状态为逆序时），需要进行n·1次排序，每次排序进行n·1比较，此时比较次数Cmax=n（n+1）/2移动次数Mmax=3n（n+1）/2，所以时间复杂度为O（n2）。

常见时间复杂度大小关系：O（1）＜O（logn）＜O（n）＜O（nlogn）＜O（n2）＜O（n3）＜O（In）＜O（n！）＜O（nn）

算法的时间复杂度和两个因素有关：算法中的最大嵌套循环层数；最大嵌套循环结构中每次循环的次数。一般来说，具有多项式时间复杂度的算法是可以接受的；具有指数时间复杂度的算法，只有当n足够小时才可以使用。一般效率较好的算法要控制在O（N）或者O（log2N）

2.空间复杂度

空间复杂度（Space Complexity）是对一个算法在运行过程中临时占用存储空间大小的量度，记做S（n）=O（f（n））。其中，n为问题规模，f（n）为语句关于n所占存储空间的函数。

算法的空间复杂度分析方法和算法的时间复杂度分析方法基本相同。

例如：

上方代码中，仅需为变量i、j、temp分配空间即可，所以空间复杂度S（n）=O（1）。