大O记法

为了统一描述，大O不关注算法所用的时间，只关注其所用的步数。

比如数组不论多大，读取都只需1步。用大O记法来表示，就是：O(1)很多人将其读作“大O1”，也有些人读成“1数量级”。一般读成“O1”。虽然大O记法有很多种读法，但写法只有一种。O(1)意味着一种算法无论面对多大的数据量，其步数总是相同的。就像无论数组有多大，读取元素都只要1步。这1步在旧机器上也许要花20分钟，而用现代的硬件却只要1纳秒。但这两种情况下，读取数组都是1步。其他也属于O(1)的操作还包括数组末尾的插入与删除。无论数组有多大，这两种操作都只需1步，所以它们的效率都是O(1)。

下面研究一下大 O 记法如何描述线性查找的效率。线性查找在数组上要逐个检查每个格子。在最坏情况下，线性查找所需的步数等于格子数。即如前所述：对于N个元素的数组，线性查找需要花N步。用大O记法来表示，即为：O(N)将其读作“O N”。若用大O记法来描述一种处理一个N元素的数组需花N步的算法的效率，很简单，就是O(N)。

常数时间与线性时间

从 O(N)可以看出，大 O记法不只是用固定的数字（如22、440）来表示算法的步数，而是基于要处理的数据量来描述算法所需的步数。或者说，大O解答的是这样的问题：当数据增长时，步数如何变化？O(N)算法所需的步数等于数据量，意思是当数组增加一个元素时，O(N)算法就要增加1步。而O(1)算法无论面对多大的数组，其步数都不变。

下图展示了这两种时间复杂度。

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

因为大O主要关注的是数据量变动时算法的性能变化，所以你会发现，即使一个算法的恒定步数不是1，它也可以被归类为O(1)。假设有个算法不能1步完成，而要花3步，但无论数据量多大，它都需要3步。如果用图形来展示，该算法应该是这样：

因为不管数据量怎样变化，算法的步数都恒定，所以这也是常数时间，也可以表示为O(1)。虽然从技术上来说它需要3步而不是1步，但大O记法并不纠结于此。简单来说，O(1)就是用来表示所有数据增长但步数不变的算法。

如果说只要步数恒定，3步的算法也属于 O(1)，那么恒为100步的算法也属于 O(1)。虽然100步的算法在效率上不如1步的算法，但如果它的步数是恒定的，那么它还是比O(N)更高效。

为什么呢？如图所示。

对于元素量少于100的数组，O(N)算法的步数会少于100步的O(1)算法。当元素刚好为100个时，两者的步数同为100。而一旦超过100个元素，注意，O(N)的步数就多于O(1)。

因为数据量从这个临界点开始，直至无限，O(N)都会比O(1)花更多步数，所以总体上来说，O(N)比O(1)低效。

这对于步数恒为1000000的O(1)算法来说也是一样的。当数据量一直增长时，一定会到达一个临界点，使得O(N)算法比O(1)算法低效，而且这种落后的状况会持续到数据量无限大的时候。