常见算法的时间复杂度_时间复杂度各阶

类型

意义

举例

O(1)

最低复杂度，耗时/耗空间与数据的大小无关，无论输入的数据增大多少倍耗时还是空间都不变。

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

O(log n)

当数据增大n倍时，耗时增大logn倍（log是以2为底的），也就是n/long。

二分查找算法就是O(log n)算法，每找一次都排除一半的可能。如256个数据找8次就能找到目标

O(n)

数据量增大几倍，耗时也增大几倍

遍历算法普通的for循环

O(n log N)

将时间复杂度为O(log n)的代码循环N遍，比如数据增大256倍时，耗时增大256*8倍。

归并排序、快速排序、堆排序

O(n^2)

对n个数的排序，需要循环n*n次

冒泡排序、插入排序、选择排序

O(n^3)

同上，相当于三层n循环。

常规的矩阵乘算法

O(n^k)

同上，相当于k层n循环

O(2^n)

常见的时间复杂度，由大到小依次为：1 < log2N < n < n*Log2N < n^2 < n^3 < 2^n < 3^n < n!