【从0到1学算法】大O表示法

KENDOEVERTHING

6年程序员，搬砖砖家，同时也是数码科技爱好者。

一般我们在选择算法时，都是想要选择效率最高的算法。那算法的效率，用什么表示？没错!就是用大O表示法。

PS : 大O表示法中，log即为log2，后面不再说明。

下面以简单查找和二分查找，在含有n个元素的有序列表中查找其中一个元素为例，下表总结了我们发现的情况。

使用简单查找时,最多需要猜测次数与列表长度相同,这被称为线性时间，大O表示法为O(n)。

二分查找则不同,最多需要猜测次数为logn（n为列表长度），这被称为对数时间（log时间），大O表示法为O(logn)。

大O表示法指出了算法的速度有多快。

可能你会好奇，它的单位是多少？秒？没有单位，它并非指的是时间，而是从增量的角度衡量。

列表中查找元素，简单查找、二分查找的增速如下图。

假若我们不知道增速,只知道查找100个元素时的查找时间,猜测10000个元素时的查找时间：

对于简单查找,100个元素时为100毫秒,简单推算出10000个元素为10秒；

对于二分查找,100个元素时为7毫秒,简单推算出10000个元素为700毫秒。

PS:简单推算 10000个元素时的运行时间= 运行时间（100个元素时）* 100

简单查找的推算是对的,因为的增速是n，而二分查找的推算是错的，它的增速为logn，这便不能理所当然简单推算了。

很显然，我们只要知道算法的增速，便能知道它在n个元素中运行的运行时间了，大O表示法就是用来表示算法增速的。

专业描述:大O表示法表示操作数的增速，指出了算法运行时间的增速。

上述的大O表示法都是用来表示 时间复杂度 ，而且通常指的是最坏情况下的时间复杂度。

通常有以下3种时间复杂度：

以简单查找为例子，在n个元素的列表中查找目标元素

下面简单分析下：目标元素如果在列表中，出现的位置有n种情况，加上不在列表中这一种情况，总共n+1种情况。每种情况下需要遍历的次数如下表：

平均遍历次数=各种情况遍历次数相加÷总的情况数

各种情况遍历次数相加为 ((1+2+3...+n)+n) ，总的情况数 (n+1)

平均情况复杂度为:

((1+2+3...+n)+n)/(n+1)=n(n+3)\2(n+1)

大O表示法，会 省略系数、低阶、常量， 所以平均情况时间复杂度是 O(n) 。

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度，反映的是一个趋势。

空间复杂度比较常用的有：O(1)、O(n)、O(n²)，我们下面来看看：

空间复杂度 O(1)

如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为 O(1)。

例子：

int i = 1;
int j = 2;