使用大 O 表示法衡量某个算法的复杂度，其实就是将该算法的运行时间用输入量为 n 的函数表示出来。这里的输入量 n 在 STL 中通常指的是算法操作的元素个数。
举个例子，当算法运行时间随元素个数成线性增长时（即如果元素个数呈倍数增长，运行时间也呈倍数增长），该算法的复杂度用 O(n) 来表示；反之，如果算法的运行时间和输入量 n 无关，则该算法的复杂度就用 O(1) 来表示。
常见的算法复杂度表示：
| 算法复杂度种类 | 含意 | 大 O 表示法 |
|---|---|---|
| 常数阶 | 算法运行时间和所操作的元素个数无关 | O(1) |
| 对数阶 | 算法运行时间随所操作的元素个数呈对数增长 | O(log(n)) |
| 线性阶 | 算法运行时间随所操作的元素个数呈线性增长 | O(n) |
| 指数阶（m次方，m为数字） | 算法运行时间随所操作的元素个数呈 m 次方增长 O(nm) | 常见的有 O(n2)、O(n3) 等 |
大 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 |
当算法处理的元素较少时，各复杂度的差别很小，此时算法效率的优劣往往受被大 O 表示法忽略部分的影响更大。而当处理元素个数越多，各复杂度的差别越大，此时复杂度被忽略的部分就变得无关紧要了。
因此，在考量算法的复杂度时，输入量 n （操作元素的个数）的值必须足够大才有意义。
最后
以上就是忧郁翅膀最近收集整理的关于衡量算法执行效率，大 O 表示法的全部内容，更多相关衡量算法执行效率，大内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复