影响算法性能的主要因素是其所需的步数。一个算法的步数并不是固定的。以线性查找为例，它的步数等于数组的元素数量。
如果数组有22 个元素，线性查找就需要22 步；如果数组有400 个元素，线性查找就需要400 步。
量化线性查找效率的更准确的方式应该是：对于具有N 个元素的数组，线性查找最多需要N步。
表达数据结构和算法的时间复杂度一种简洁又通用的方式是大O记法，可以指出一个算法的性能级别。
掌握了大O 记法，就掌握了算法分析的专业工具。
大O 记法源于数学领域。大O 记法可用来描述一个函数的增长率的上限，或者“如果函数g(x)的增长速度不比函数f(x)快，那么就称g 属于O( f )”。
大O 不关注算法所用的时间，只关注其所用的步数。
数组不论多大，读取都只需1 步。用大O 记法来表示，就是O(1)
很多人将其读作“大O1”，也有些人读成“1 数量级”。一般读成“O1”。虽然大O 记法有很多种读法，但写法只有一种。
O(1)意味着一种算法无论面对多大的数据量，其步数总是相同的。就像无论数组有多大，读取元素都只要1 步。这1 步在旧机器上也许要花20 分钟，而用现代的硬件却只要1 纳秒。但这两种情况下，读取数组都是1 步。
其他也属于O(1)的操作还包括数组末尾的插入与删除。之前已证明，无论数组有多大，这两种操作都只需1 步，所以它们的效率都是O(1)。
线性查找在数组上要逐个检查每个格子。在最坏情况下，线性查找所需的步数等于格子数。即如前所述：对于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)低效。
这对于步数恒为1 000 000 的O(1)算法来说也是一样的。当数据量一直增长时，一定会到达一个临界点，使得O(N)算法比O(1)算法低效，而且这种落后的状况会持续到数据量无限大的时候。
原文：https://www.cnblogs.com/hlaotong/p/12621356.html