前面有两篇总结了排序算法，最近刚好在看《算法图解》，想由表及里整理一份算法系列。每次介绍算法时，都会讨论其运行时间，一般而言，应选择效率最高的算法，以最大限度地减少运行时间或占用空间。那怎么表示算法的速度呢，今天来了解一下：大O表示法。

理解大O表示法

大O表示法是一种特殊的表示法，指出了算法的速度有多快。我们举个例子：假设列表包含n个元素，简单的查询需要检查每个元素，因此需要执行n次操作。使用大O表示法，这个运行时间为：O(n)。单位？没有，大O表示法指的是算法运行时间的增速，不需要单位来描述。

我们再来看一个例子：为检查长度为n的列表元素，我们来使用二分查找，需要执行(log n)次操作。那么使用大O表示法，这个运行时间为：O(log n)，这指出了算法需要执行的操作数。

大O表示法指出最糟糕情况下的运行时间

又举个例子：假如使用简单查找的方法，上面说过，简单查找的运行时间为O(n)，这意味着在最糟的情况下，必须查看每一个元素。如果我们要找到1024这个数字，刚好第一个数字就是我们要找的，那这种算法的运行时间是O(n)还是O(1)呢？这里我们总结一下，简单查找的运行时间总是为O(n)，查找1024元素时，一次就找到了，这是最佳的情况，但大O表示法表示的是最糟的情形。我们可以这样说：简单查找的运行时间不可能超过O(n)。

除了最糟的情况下的运行时间，我们还得考虑平均情况的运行时间。

一些常见的大O的运行时间

• O(log n)，也叫对数时间，这样的算法包括二分查找。
• O(n)，也叫线性时间，这样的算法包括简单查找。
• O(n * log n)，这样的算法包括快速排序。
• O(n^2)，这样的算法包括选择排序。
• O(n!)，这样的算法包括旅行商问题的解决方案，也是我即将学习的。
• ……

小结

当然了，我们在前面是将大O运行时间表示转换为操作数来理解，我们小结一下：

• 算法的速度指的并非时间，而是操作数的增速。
• 谈论算法的速度时，我们说的是随着输入的增加，其运行时间将以什么样的速度增加。
• 算法的运行时间用法大O表示法表示。