赵走x博客 - 开发者的网上家园

Python性能分析与优化：4、运行时间复杂度

资源编号:75724 书籍 Python性能分析与优化热度：143

在进行性能分析和优化时，理解运行时间复杂度（Running Time Complexity，RTC）的知识，以及学习使用它们适当地优化代码十分重要。

## **1.6　运行时间复杂度**

在进行性能分析和优化时，理解运行时间复杂度（Running Time Complexity，RTC）的知识，以及学习使用它们适当地优化代码十分重要。

RTC可以用来对算法的运行时间进行量化。它是对算法在一定数量输入条件下的运行时间进行数学近似的结果。因为是数学近似，所以我们可以用这些数值对算法进行分类。

RTC常用的表示方法是**大O标记**（big O notation）。数学上，大O标记用于表示包含无限项的函数的有限特征（类似于泰勒展开式）。如果把这个概念用于计算机科学，就可以把算法的运行时间描述成渐进的有限特征（数量级）。

也就是说，这种标记通过宽泛的估计，让我们了解算法在任意数量输入下的运行时间。但是它不能提供精确的时间值，需要对代码进行深入的分析才能获得。

前面说过，用这种标记方法可以对算法进行分类，下面就是常用的算法类型。

### **1.6.1　常数时间——*O*(1)**

常数时间（constant time）是最简单的算法复杂度类型。这基本上表示我们的测量结果将是恒定值，算法运行时间不会随着输入的增加而增加。

运行时间为*O*(1)的代码示例如下所示。

* 判断一个数是奇数还是偶数：
    
    ```
    if number % 2:
        odd = True
    else:
        odd = False
    
    ```
    
* 用标准输出方式打印信息：
    
    ```
    print("Hello world!")
    ```

对于理论上更复杂的操作，比如在字典（或哈希表）中查找一个键的值，如果算法合理，就可以在常数时间内完成。技术上看，在哈希表中查找元素的消耗时间是*O*(1)平均时间，这意味着每次操作的平均时间（不考虑特殊情况）是固定值*O*(1)。

### **1.6.2　线性时间——*O*(*n*)**

线性时间复杂度表示，在任意 *n* 个输入下，算法的运行时间与 *n* 呈线性关系，例如，3*n*，4*n*+5，等等。

![image.png](https://img.hacpai.com/file/2019/08/image-868ee60f.png)

如上图所示，当 *x* 轴无线延伸时，蓝线（3*n*）和红线（4*n*+5）会和黑线（*n*）达到同样的上限。因此，为了简化，我们把这些算法都看成*O*(*n*)类。

这种数量级（order）的算法案例有：

* 查找无序列表中的最小元素
    
* 比较两个字符串
    
* 删除链表中的最后一项

### **1.6.3　对数时间——*O*(log*n*)**

对数时间（logarithmic time）复杂度的算法，表示随着输入数量的增加，算法的运行时间会达到固定的上限。随着输入数量的增加，对数函数开始增长很快，然后慢慢减速。它不会停止增长，但是越往后增长的速度越慢，甚至可以忽略不计。

![image.png](https://img.hacpai.com/file/2019/08/image-8cb92833.png)

上图显示了三种不同的对数函数。你会看到三条线都是同样的形状，随着*x*的增大，都是无限增加的。

对数时间的算法示例如下所示：

* 二分查找（binary search）
    
* 计算斐波那契数列（用矩阵乘法）

### **1.6.4　线性对数时间——*O*(*n* log*n*)**

把前面两种时间类型组合起来就变成了线性对数时间（linearithmic time）。随着 *x* 的增大，算法的运行时间会快速增长。

这类算法的示例如下所示：

* 归并排序（merge sort）
    
* 堆排序（heap sort）
    
* 快速排序（quick sort，至少是平均运行时间）

下图中的线性对数函数曲线可以让我们更好地理解这类算法。

![image.png](https://img.hacpai.com/file/2019/08/image-4ce29a4f.png)

### **1.6.5　阶乘时间——*O*(*n*!)**

阶乘时间（factorial time）复杂度的算法是最差的算法。其时间增速特别快，图都很难画。

下图是对阶乘函数的近似描述，可以看成这类算法的运行时间。

![image.png](https://img.hacpai.com/file/2019/08/image-9d836c98.png)

阶乘时间复杂度的一个示例，就是用暴力破解搜索方法解货郎担问题（遍历所有可能的路径）。

### **1.6.6　平方时间——*O*(*n*2)**

平方时间是另一个快速增长的时间复杂度。输入数量越多，需要消耗的时间越长（大多数算法都是这样，这类算法尤其如此）。平方时间复杂度的运行效率比线性时间复杂度要慢。

这类算法的示例如下：

* 冒泡排序（bubble sort）
    
* 遍历二维数组
    
* 插入排序（insertion sort）

这类函数的曲线图如下所示：

![image.png](https://img.hacpai.com/file/2019/08/image-7d16f841.png)

最后，我们把所有算法运行时间复杂度放在一张图上，比较一下运行效率：

![image.png](https://img.hacpai.com/file/2019/08/image-cd3be0f1.png)

不考虑常数时间复杂度（虽然它是最快的，但是显然复杂算法都不可能达到这个速度），那么时间复杂度排序如下所示：

* 对数
    
* 线性
    
* 线性对数
    
* 平方
    
* 阶乘

有时候，你可能也没办法，只能选择平方时间复杂度作为最佳解决方案。理论上我们总是希望实现更快速的算法，但是问题和技术的限制往往会影响结果。

> 注意，平方时间类型与阶乘时间类型之间，有一些变体，如三次方时间类型、四次方时间类型等。

还有很重要的一点需要考虑，就是算法的时间复杂度往往不止一种类型，可能是三种类型，包括最好情况、正常情况和最差情况。三种情况是由输入条件的不同属性决定的。例如，如果结果已经排序，插入排序算法的运行速度会比较快（最好情况），其他情况则要更慢一些（指数复杂度）。

另外数据类型也会影响时间复杂度。算法运行时间复杂度也与实际的操作方式有关（索引、插入、搜索等）。常见的数据类型和操作的时间复杂度如下所示。

![image.png](https://img.hacpai.com/file/2019/08/image-c8b20731.png)