背景

去年下半年，我在微信书架里加入了许多技术书籍，各种类别的都有，断断续续的读了一部分。

没有计划的阅读，收效甚微。

新年伊始，我准备尝试一下其他方式，比如阅读周。每月抽出1~2个非连续周，完整阅读一本书籍。

这个“玩法”虽然常见且板正，但是有效，已经坚持阅读七个月。

已读完书籍：《架构简洁之道》、《深入浅出的Node.js》、《你不知道的JavaScript（上卷）》、《你不知道的JavaScript（中卷）》、《你不知道的JavaScript（下卷）》、《数据结构与算法JavaScript描述》、《WebKit技术内幕》、《前端架构：从入门到微前端》。

当前阅读周书籍：《秒懂算法：用常识解读数据结构与算法》。

大O记法

大O：对N个元素来说需要多少步

大O用一种特别的方法关注算法需要的步骤数，借此达成一致性。我们先用大O分析线性查找算法。

在最坏的情况下，数组中有多少个元素，线性查找就需要多少步。正如先前所述：对于有N个元素的数组，线性查找最多需要N步。用大O记法来表示就是：O(N)。

O(N)意味着核心问题的答案是“算法需要N步”。

下面仍以线性查找为例，来快速回顾一下用大O记法表示时间复杂度的思维过程。首先，提出核心问题：如果数组中有N个数据元素，那么线性查找需要多少步？因为答案是N步，所以将其时间复杂度表示为O(N)。这里提一句，时间复杂度O(N)的算法也被称为线性时间算法。

我们来对比一下从标准数组中读取这一操作的时间复杂度。无论数组有多大，读取都只需要1步。想用大O记法表示这个复杂度，还需从核心问题开始：如果有N个数据元素，那么从数组中读取需要多少步呢？因为答案是1，所以写成O(1)。我把它读作“O1”。

无论数组中有多少个数据元素，从数组中读取总是需要1步。这就是O(1)被认为是“最快”的一类算法的原因。即便数据量增加，O(1)算法也不需要额外的步骤。无论N是多少，O(1)算法的步骤数都是固定的。事实上，O(1)算法也被称作常数时间算法。

大O的灵魂

大O的灵魂才是其真正含义：随着数据的增加，算法性能会如何变化？

这才是大O的灵魂所在。大O不仅会告诉你算法需要的步骤数，还会告诉你数据变化时步骤数的变化。

从这个角度来看，我们其实根本不在意算法到底是O(1)还是O(3)。因为两个算法的步骤数都不受数据量增加的影响，所以它们是复杂度相同的算法。无论数据如何，它们的步骤数都是常数，所以无须区分二者。

O(N)的算法和它们就不同了。这个算法的性能会随着数据增加而变化。更确切地说，数据增加时，这个算法步骤数的增加量和数据的增加量成正比。这就是O(N)的含义。它表示出了数据和算法效率之间的比例关系，准确地描述了数据增加时步骤数增加的幅度。

深入大O的灵魂

对于少于100个元素的数据集，O(N)算法需要的步骤数要少于这个100步的O(1)算法。元素数达到100时，两条线相交。这意味着两者都需要100步。但关键在于：对于所有多于100个元素的数组，O(N)算法都需要更多步骤。

在数据达到一定量之后，形势总是会逆转，O(N)算法在那之后永远都需要更多步。因此，总体来说，无论O(1)算法要花多少步，我们都认为O(N)的效率比O(1)低

同样的算法，不同的场景

如前所述，线性查找不总是O(N)算法。如果要找的元素在数组的最后一个格子，那么线性查找确实需要N步。但如果它在第一个格子，那么线性查找就只需要1步。因此，这种情况下的线性查找就是一个O(1)算法。如果要整体描述线性查找的效率，那么我们会说它在最好情况下是O(1)，最坏情况下是O(N)。

虽然大O既可以描述最好情况，也可以描述最坏情况，但除非特别注明，大O记法一般指的都是最坏情况。因此，即便线性查找在最好情况下是O(1)算法，大多数参考资料还是把它算作O(N)算法。

对数

二分查找这样的算法被描述为O(log N)。log是logarithm（对数）的缩写。

对数是指数的反函数。

2^3等价于2 × 2× 2，其结果是8。而log₂8则是其逆运算。它的意思是：2需要自乘多少次才能得到8？因为2需要自乘3次才能得到8，所以log₂8 = 3。

O(log N)的含义

O(log N)的意思是，对于N个数据元素，算法需要log₂N步。如果有8个元素，因为log₂8 = 3，所以算法需要3步。

换言之，如果一直把8个元素等分，那么需要3步才能得到1个元素。这正是二分查找的过程。当查找某个元素时，一直等分数组的格子，直到找到正确的数。

换言之，如果一直把8个元素等分，那么需要3步才能得到1个元素。这正是二分查找的过程。当查找某个元素时，一直等分数组的格子，直到找到正确的数。

O(N)算法需要的步骤数和元素个数一样多，而每次数据量加倍时，O(log N)算法只需要额外增加1步。

总结

大O记法为比较算法提供了一个统一的框架。我们可以使用大O来考察实际情景，选择合适的数据结构和算法，让代码更高效、处理的数据更多。

作者介绍
非职业「传道授业解惑」的开发者叶一一。
《趣学前端》、《CSS畅想》等系列作者。华夏美食、国漫、古风重度爱好者，刑侦、无限流小说初级玩家。
如果看完文章有所收获，欢迎点赞👍 | 收藏⭐️ | 留言📝。