常见算法的时间复杂度 Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…

￡神魔★判官ぃ 2022-01-05 05:31 213阅读 0赞

关于时间复杂度，有一个公式：T (n) = Ο(f (n))。  
为了便于比较同一问题的不同算法，通常从算法中抽取一种或者多种有代表性的基本操作，再以这些基本操作重复执行的次数与问题规模的关系T(n) 作为算法的时间性量度。  
如果T(n) 和 f(n) 是n 的函数，当n →∞ 时，有T(n) / f(n) → c (常数c ≠ 0)，记作：T(n) = O(f(n))，称O(f(n)) 为算法的渐近时间复杂度，简称时间复杂度。  
  
算法的空间复杂度：  
一个算法实现所占存储空间大致包含三方面：  
1. 指令、常数、变量所占用的存储空间；  
2. 输入数据所占用的存储空间；  
3. 算法执行时所需的辅助空间；  
前两者是必须的，通常将算法执行时所需的辅助空间作为分析算法空间复杂度的依据：S(n) = O(f(n))，其中f(n)的规则与时间复杂度一致。

所以，我们就先来看看 O(1) 是什么意思？算法的时间复杂度：

### 1.O(1) ###

O(1) 也就是最低时间复杂度。代表的是一个常量值。也就是说耗时，耗空间与输入数据的大小无关。无论输入数据增大多少倍，耗时是不变的。

相关算法举例：哈希算法（不考虑冲突的情况），无论在数据量多么大，都是 O(1)。

### 2.O(n) ###

O(n) 理解起来也很简单，就是算法的时间复杂度随着数据量的增大几倍，耗时也增大几倍。

常见的算法举例：遍历算法。

### 3.O(n^2) ###

就代表数据量增大 n 倍时，耗时增大 n 的平方倍，这是比线性更高的时间复杂度。比如冒泡排序，就是典型的 O(n^2) 的算法，对 n 个数排序，需要扫描 n × n 次。

O(n^2) 也有人用 O(n²) 表示。这两个表示是一样的。

### 4.O(logn) ###

当数据增大 n 倍时，耗时增大 logn 倍（这里的 log 是以 2 为底的，比如，当数据增大 256 倍时，耗时只增大 8 倍，是比线性还要低的时间复杂度）。二分查找就是 O(logn)的算法，每找一次排除一半的可能，256 个数据中查找只要找 8 次就可以找到目标。

### 5.O(nlogn) ###

O(nlogn) 就是 n 乘以 logn，当数据增大 256 倍时，耗时增大 256\*8=2048 倍。这个复杂度高于线性低于平方。归并排序就是 O(nlogn) 的时间复杂度。

常见的时间复杂度有：常数阶 O(1)，对数阶 O(log2n)，线性阶 O(n)，线性对数阶 O(nlog2n)，平方阶 O(n2)，立方阶 O(n3)，…，k 次方阶 O(nk)，指数阶 O(2n) 等。我就不一一列举说明了。

根据经验，我们应该尽可能选用多项式阶 O(nk) 的算法，而不希望用指数阶的算法。

常见的算法时间复杂度由小到大依次为：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTU1NjUz_size_16_color_FFFFFF_t_70][]上图是常见的算法时间复杂度举例。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTU1NjUz_size_16_color_FFFFFF_t_70]: /images/20211230/bfdf8457e27b4f71b5eef450435589bb.png