O(1), O(n), O(logn), O(nlogn) 的区别

在描述算法复杂度时，经常用到O(1), O(n), O(logn), O(nlogn)来表示对应复杂度程度，不过目前大家默认也通过这几个方式表示空间复杂度。

O加上（）的形式，里面其实包裹的是一个函数f()，O(f())，指明某个算法的耗时，空间与数据增长指间的关系。其中n代表输入数据的量。

O(1)

**解释：**最低复杂度，常量值，也就是耗时/耗空间与输入数据大小无关，无论输入数据增大多少倍，耗时/耗空间都不变。

**举例：**哈希算法就是典型的O(1)时间复杂度，无论数据规模多大，都可以在一次计算后找到目标（不考虑冲突的话）

O(n)

**解释：**数据量增大几倍，耗时也增大几倍。

**举例：**遍历算法

O(n²)

**解释：**对n个数排序，需要扫描n*n次

**举例：**冒泡排序

O(logn)

**解释：**当数据增大n倍时，耗时增大logn倍（这里的logn是以2为底的，比如当数据增大256倍的时候，耗时只增加8倍，就是8个2相乘等于256）

**举例：**二分法查找就是O(logn)的算法，没找一次排除一半的可能，256个数据中查找只要找8次就可以找到目标

O(nlogn)

**解释：**就是n乘以logn，当数据增大256倍时，耗时增大256*8=2048倍。这个复杂度高于线性低于平方。

**举例：**归并排序就是O(nlogn)的时间复杂度

注：如果ax=N(a>0,且a不等于1，那么数x就叫做以a为底N的对数，记做x=logaN,读作以a为底N的对数，其中a叫做对数的底数，N叫做真树)