Python性能分析与优化——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呈线性关系，例如，3n，4n+5，等等。 如上图所示，当x轴无线延伸时，蓝线（3n）和红线（4n+5）会和黑线（n）达到同样的上限。因此，为了简化，我们把这些算法都看成O(n)类。 这种数量级（order）的算法案例有：  查找无序列表中的最小元素  比较两个字符串  删除链表中的最后一项 1.6.3　对数时间——O(logn) 对数时间（logarithmic time）复杂度的算法，表示随着输入数量的增加，算法的运行时间会达到固定的上限。随着输入数量的增加，对数函数开始增长很快，然后慢慢减速。它不会停止增长，但是越往后增长的速度越慢，甚至可以忽略不计。 上图显示了三种不同的对数函数。你会看到三条线都是同样的形状，随着x的增大，都是无限增加的。 对数时间的算法示例如下所示：  二分查找（binary search）  计算斐波那契数列（用矩阵乘法） 1.6.4　线性对数时间——O(nlogn) 把前面两种时间类型组合起来就变成了线性对数时间（linearithmic time）。随着x的增大，算法的运行时间会快速增长。 这类算法的示例如下所示：  归并排序（merge sort）  堆排序（heap sort）  快速排序（quick sort，至少是平均运行时间） 下图中的线性对数函数曲线可以让我们更好地理解这类算法。 1.6.5　阶乘时间——O(n!) 阶乘时间（factorial time）复杂度的算法是最差的算法。其时间增速特别快，图都很难画。 下图是对阶乘函数的近似描述，可以看成这类算法的运行时间。 阶乘时间复杂度的一个示例，就是用暴力破解搜索方法解货郎担问题（遍历所有可能的路径）。 1.6.6　平方时间——O(n2) 平方时间是另一个快速增长的时间复杂度。输入数量越多，需要消耗的时间越长（大多数算法都是这样，这类算法尤其如此）。平方时间复杂度的运行效率比线性时间复杂度要慢。 这类算法的示例如下：  冒泡排序（bubble sort）  遍历二维数组  插入排序（insertion sort） 这类函数的曲线图如下所示： 最后，我们把所有算法运行时间复杂度放在一张图上，比较一下运行效率： 不考虑常数时间复杂度（虽然它是最快的，但是显然复杂算法都不可能达到这个速度），那么时间复杂度排序如下所示：  对数  线性  线性对数  平方  阶乘 有时候，你可能也没办法，只能选择平方时间复杂度作为最佳解决方案。理论上我们总是希望实现更快速的算法，但是问题和技术的限制往往会影响结果。 注意，平方时间类型与阶乘时间类型之间，有一些变体，如三次方时间类型、四次方时间类型等。 还有很重要的一点需要考虑，就是算法的时间复杂度往往不止一种类型，可能是三种类型，包括最好情况、正常情况和最差情况。三种情况是由输入条件的不同属性决定的。例如，如果结果已经排序，插入排序算法的运行速度会比较快（最好情况），其他情况则要更慢一些（指数复杂度）。 另外数据类型也会影响时间复杂度。算法运行时间复杂度也与实际的操作方式有关（索引、插入、搜索等）。常见的数据类型和操作的时间复杂度如下所示。 时间复杂度 数据结构 正常情况 最差情况 索引 查找 插入 删除 索引 查找 插入 删除 列表（list） O(1) O(n)   O(1) O(n)   单向链表（linked list） O(n) O(n) O(1) O(1) O(n) O(n) O(1) O(n) 双向链表（doubly linked list） O(n) O(n) O(1) O(1) O(n) O(n) O(1) O(1) 字典（dictionary）  O(1) O(1) O(1)  O(n) O(n) O(n) 二分查找树（Binary Search Tree，BST） O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n) O(n) O(n) O(n)