使用大 O 表示法衡量某个算法的复杂度，其实就是将该算法的运行时间用输入量为 n 的函数表示出来。这里的输入量 n 在 STL 中通常指的是算法操作的元素个数。
举个例子，当算法运行时间随元素个数成线性增长时（即如果元素个数呈倍数增长，运行时间也呈倍数增长），该算法的复杂度用 O(n) 来表示；反之，如果算法的运行时间和输入量 n 无关，则该算法的复杂度就用 O(1) 来表示。
表 1 列出了常见的算法复杂度种类，以及使用大 O 表示法表示的复杂度。
| 算法复杂度种类 | 含义 | 大 O 表示法 |
|---|---|---|
| 常数阶 | 算法运行时间和所操作的元素个数无关 | O(1) |
| 对数阶 | 算法运行时间随所操作的元素个数呈对数增长 | O(log(n)) |
| 线性阶 | 算法运行时间随所操作的元素个数呈线性增长 | O(n) |
| 指数阶（m次方，m为数字） | 算法运行时间随所操作的元素个数呈 m 次方增长 O(nm) | 常见的有 O(n2)、O(n3) 等 |
值得注意的是，大 O 表示法并不关心算法运行所消耗的具体时间，换句话说，对于那些影响算法运行效率较小的因素，使用大 O 表示法表示时会直接将其忽略。例如，某个算法运行的复杂度为 O(n)，呈线性增长，但至于线性增长的具体程度（是 100n 还是 2n），在大 O 表示法看来，它们是一样的。也就是说，采用这种测量法则，任何两个线性算法都将被视为具有相同的复杂度。
采用大 O 表示法甚至会出现这种一种情况，即带有巨大常量的线性算法，很有可能会比小常量的指数算法更受欢迎，因为该方法无法显示出真实的运行时间。
所以请读者记住，大 O 表示法只是某种度量方法，它所显示的算法的最佳复杂度，并不一定就是真正的最佳（最快）算法。
| 复杂度 | 元素个数 | |||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 种类 | 大 O 表示 | 1 | 2 | 5 | 10 | 50 | 100 | 1 000 | 10 000 | |||||
| 常量阶 | O(1) | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | |||||
| 对数阶 | O(log(n)) | 1 | 2 | 3 | 4 | 6 | 7 | 10 | 13 | |||||
| 线性阶 | O(n) | 1 | 2 | 5 | 10 | 50 | 100 | 1 000 | 10 000 | |||||
| 2次方 | O(n2) | 1 | 4 | 25 | 100 | 2500 | 10 000 | 1 000 000 | 100 000 000 | |||||
表 2 列出了常用的复杂度随元素个数增长的变化程序。可以看到，当算法处理的元素较少时，各复杂度的差别很小，此时算法效率的优劣往往受被大 O 表示法忽略部分的影响更大。而当处理元素个数越多，各复杂度的差别越大，此时复杂度被忽略的部分就变得无关紧要了。
因此，在考量算法的复杂度时，输入量 n （操作元素的个数）的值必须足够大才有意义。
原创文章，作者：奋斗，如若转载，请注明出处：https://blog.ytso.com/tech/pnotes/23716.html