2.4 时间复杂度_Python数据结构学习笔记-QQ阅读女生青春网

上QQ阅读APP看书，第一时间看更新

2.4　时间复杂度

算法的复杂度分为两种：时间复杂度和空间复杂度。时间复杂度是指执行算法所需的计算工作量，而空间复杂度是指执行这个算法所需的内存空间。在计算机科学中，时间复杂度又称时间复杂性，通常用于检验算法的的运行效率。算法的时间复杂度是一个函数，能够定性描述该算法的运行时间。时间复杂度常用大O符号表述，是一个代表算法输入值的字符串长度的函数，不包括这个函数的低阶项和首项系数。

↑扫码看视频（本节视频课程时间：6分09秒）

2.4.1　寻找最优算法

程序是用来解决问题的，由多个步骤或过程组成，这些步骤和过程就是解决问题的算法。一个问题有多种解决方法，也就会对应有多种算法。每一种算法都可以达到解决问题的目的，但花费的成本和时间不尽相同。我们可以从节约成本和时间的角度进行考虑，找出最优的一种算法。那么，究竟如何衡量一个算法的好坏呢？显然，首先必须确保选用的算法应该是正确的（算法的正确性不在此论述）。除此之外，通常还需要从以下三个方面进行考虑：

（1）算法在执行过程中所消耗的时间；

（2）算法在执行过程中所占资源的大小，例如占用内存空间的大小；

（3）算法的易理解性、易实现性和易验证性等。

衡量一个算法的好坏，可以通过上述三个方面进行综合评估。从多个候选算法中找出运行时间短、资源占用少、易理解、易实现的算法。但是现实情况总是不尽如人意，往往是一个看起来很简便的算法，其运行时间要比一个形式上复杂的算法慢得多；而一个运行时间较短的算法往往占用较多的资源。因此，在不同情况下需要选择不同的算法：

●在实时系统中，对系统响应时间要求高，则尽量选用执行时间少的算法；

●当数据处理量大，而存储空间较少时，则尽量选用节省空间的算法。本书将主要讨论算法的时间特性，并给出算法在时间复杂度上的度量指标。

一个算法在执行过程中所消耗的时间，主要取决于以下因素：

（1）算法所需数据输入的时间。

（2）算法编译为可执行程序的时间。

（3）计算机执行每条指令所需的时间。

（4）算法语句重复执行的次数。

其中（1）依赖于输入设备的性能，若是脱机输入，则输入数据的时间可以忽略不计。（2）和（3）取决于计算机本身执行的速度和编译程序的性能。因此，习惯上将算法语句重复执行的次数作为算法的时间量度。

2.4.2　常见算法的时间复杂度

在计算机编程语言中，通用的计算时间复杂度的步骤如下。

（1）用常数1代替运行时间中的所有加法常数。

（2）修改后的运行次数函数中，只保留最高阶项。

（3）去除最高阶项的系数。

在各种不同的算法中，如果算法语句的执行次数为常数，则算法的时间复杂度为O（1），按数量级递增排列。在现实应用中，常见算法的时间复杂度如下：

（1）O（1）：常量阶，运行时间为常量；

（2）O（logn）：对数阶，如二分搜索算法；

（3）O（n）：线性阶，如n个数内找最大值；

（4）O（nlogn）：对数阶，如快速排序算法；

（5）O（n2）：平方阶，如选择排序，冒泡排序；

（6）O（n3）：立方阶，如两个n阶矩阵的乘法运算；

（7）O（2n）：指数阶，如n个元素集合的所有子集的算法；

（8）O（n！）：阶乘阶，如n个元素全部排列的算法。

在表2-1中列出了几种主流算法的时间复杂度和空间复杂度。

表2-1　主流算法的时间复杂度和空间复杂度

2.4.3　实战演练——用Python体验时间复杂度

因为本书是基于Python语言讲解的，所以下面以Python代码为基础，演示时间复杂度在程序中的意义。在下面的实例文件timefu.py中，标注出Python语言中几种常用语句的时间复杂度。

在编程语言中，几次循环就是n的几次方的时间复杂度，如在上面代码中设置n的值是3。例如，在下面的实例文件n.py中，设置n的值是64。

因为26=64，log264=6，所以循环减半的时间复杂度为O（log2n），即简写为O（logn）。如果是循环减半的过程，时间复杂度为O（logn）或O（log2n）。常见的时间复杂度由高到低的排序为：

O（1）<O（logn）<O（n）<O（nlogn）<O（n2）<O（n3）<O（2n）<O（n！）<O（nn）

另外，在Python语言中有一个内置模块库timeit，用来检测和比较一小段Python代码的运行时间（注意，程序运行的时间也跟计算机的配置有很大的关系）。在Python程序中，可以考虑使用timeit来计算程序的运行时间，在同一台计算机下，比较各种算法的运行效率。下面是内置模块库timeit的语法格式：