大 O 表示法

一般用大 O 表示法来描述复杂度，简单估算算法的执行效率；使用大 O 时间复杂度实际上并不具体表示代码真正的执行时间，而是 表示 代码执行时间随数据规模增长的变化趋势 ，所以也叫作 渐进时间复杂度；空间复杂度则表示算法的存储空间与数据规模之间的增长关系。

:::info T(n) = O(f(n)) :::

使用大 O 表示法：

  • 忽略常数，系数
  • 总复杂度为量级最大的复杂度（忽略低阶）
  • 对数阶省略底数 ( log2n) =>( logn ) | 执行次数 | 复杂度 | 量级 | | —- | —- | —- | | 12 | O(1) | 常数阶 | | 2n+1 | O(n) | 线性阶 | | 3n2+4n+9 | O(n2) | 平方阶 | | 2log2n+12 | O(logn) | 对数阶 | | nlog2n+2n+5 | O(nlogn) | 线性对数阶 | | 2n | O(2n) | 指数阶 | | | O(n!) | 阶乘阶 |

趋势对比图

complexity.png
O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(2n) < O(n!)