第3章 大O记法

量化线性查找效率的方式应该是：对于具有N个元素的数组，线性查找最多需要N步。

为了方便表达数据结构和算法的时间复杂度，计算机科学家从数学界借鉴了一种简洁又通用的方式，那就是大O记法。这种规范化语言使得我们可以轻松地指出一个算法的性能级别。

3.1 大O：数步数

为了统一描述，大O不关注算法所用的时间，只关注其所用的步数。数组不论多大，读取都只需1步。用大O记法来表示，就是：O(1)。O(1)意味着一种算法无论面对多大的数据量，其步数总是相同的。这1步在旧机器上也许要花20分钟，而用现代的硬件却只要1纳秒。但这两种情况下，读取数组都是1步。

线性查找在数组上要逐个检查每个格子。在最坏情况下，线性查找所需的步数等于格子数。即如前所述：对于N个元素的数组，线性查找需要花N步。用大O记法来表示，即为：O(N)。

3.2 常数时间与线性时间

从 O(N)可以看出，大 O记法不只是用固定的数字来表示算法的步数，而是基于要处理的数据量来描述算法所需的步数。或者说，大O解答的是这样的问题：当数据增长时，步数如何变化？

从图中可以看出，O(N)呈现为一条对角线。当数据增加一个单位时，算法也随之增加一步。也就是说，数据越多，算法所需的步数就越多。O(N)也被称为线性时间。相比之下，O(1)则为一条水平线，因为不管数据量是多少，算法的步数都恒定。所以，O(1)也被称为常数时间。

如果说只要步数恒定，3步的算法也属于 O(1)，那么恒为100步的算法也属于O(1)。虽然100步的算法在效率上不如1步的算法，但如果它的步数是恒定的，那么它还是比O(N)更高效，因为当数据量一直增长时，一定会到达一个临界点，使得O(N)算法比O(1)算法低效，而且这种落后的状况会持续到数据量无限大的时候。

3.3 同一算法，不同场景

线性查找并不总是O(N)的。当要找的元素在数组末尾，那确实是O(N)。但如果它在数组开头，1步就能找到的话，那么技术上来说应该是O(1)。所以概括来说，线性查找的最好情况是O(1)，最坏情况是O(N)。虽然大 O可以用来表示给定算法的最好和最坏的情景，但若无特别说明，大 O记法一般都是指最坏情况。因此尽管线性查找有O(1)的最好情况，但大多数资料还是把它归类为O(N)。

这种悲观主义其实是很有用的：知道各种算法会差到什么程度，能使我们做好最坏打算，以选出最适合的算法。

3.4 第三种算法

二分查找的大O记法是：O(logN)。归于此类的算法，它们的时间复杂度都叫作对数时间。简单来说，O(log N)意味着该算法当数据量翻倍时，步数加1。

3.5 对数

log即是对数（logarithm）,先回顾一下指数。

2³等于：2×2×2，结果为8。

log₂8则将上述计算反过来，它意思是：要把2乘以自身多少次，才能得到8。因为需要3次，所以，log₂8=3。

2⁶可以解释为：2×2×2×2×2×2=64，因为2要乘以自身6次才得到64，所以，log₂64=6。

不过以上都是教科书式的定义，换一种更形象和更易于理解的方式来解释。

**log₂8可以表达为：将8不断地除以2直到1，需要多少个2。**8 / 2 / 2 / 2=1（注：按照从左到右的顺序计算），或者说，将8不断地除以2，要除多少次才能到1呢？答案是3，所以，log₂8=3。

类似地，log_{2<64可以解释为：将64除以2多少次，才能得到1。64 / 2 / 2 / 2 / 2 /2 / 2=1，因为这里有6个2，所以，log264=6。}

3.6 解释O(log N)

当我们说O(log N)时，其实指的是O(log₂N)，不过为了方便就省略了2而已。

O(N)代表算法处理N个元素需要N步。如果元素有8个，那么这种算法就需要8步。

O(logN)则代表算法处理N个元素需要log₂N步。如果有8个元素，那么这种算法需要3步，因为log28=3。

从另一个角度来看，如果要把8个元素不断地分成两半，那么得拆分3次才能拆到只剩1个元素。这正是二分查找所干的事情。它就是不断地将数组拆成两半，直至范围缩小到只剩你要找的那个元素。

简单来说，O(logN)算法的步数等于二分数据直至元素剩余1个的次数。

对比O(N)和O(log N)的效率，每次数据量翻倍时，O(N)算法的步数也跟着翻倍，O(log N)算法却只需加1。

3.7 实例 （略）

3.8 总结

学会大O记法，我们在比较算法时就有了一致的参考系。有了它，就可以在现实场景中测量各种数据结构和算法，写出更快的代码，更轻松地应对高负荷的环境。