如何衡量一个算法的执行效率？

大 O 表示法（算法复杂度分析）

学习 C++ 标准库，尤其是 STL 时，经常需要考量算法和成员函数的效能（即运行效率，也称复杂度）。因此每个学习 STL 的读者都需要掌握一种衡量算法（或成员函数）复杂度的方法，目前最常用的方法称为大 O 表示法（注意，不是数字 0，而是字母 O）。

---

一、什么是大 O 表示法？

使用大 O 表示法衡量某个算法的复杂度，就是将该算法的运行时间用输入量为 n 的函数表示出来。这里的输入量 n 在 STL 中通常指的是算法所操作的元素个数。

例如：

• 当算法运行时间随元素个数成线性增长时（即元素个数呈倍数增长，运行时间也呈倍数增长），该算法复杂度用 O(n) 表示。
• 若算法运行时间与输入量 n 无关，则该算法复杂度为 O(1)。

---

二、常见算法复杂度种类（大 O 表示法）

表 1：常见算法复杂度种类及其含义

算法复杂度种类	含义	大 O 表示法
常数阶	算法运行时间和所操作元素个数无关	O(1)
对数阶	算法运行时间随所操作元素个数呈对数增长	O(log(n))
线性阶	算法运行时间随所操作元素个数呈线性增长	O(n)
指数阶（m 次方，m 为数字）	算法运行时间随所操作元素个数呈 m 次方增长，例如常见的有 O(n²)、O(n³) 等	O(nᵐ)

---

三、大 O 表示法的特点（注意事项）

值得注意的是，大 O 表示法并不关心算法运行所消耗的具体时间。换句话说，对于那些影响算法运行效率较小的因素，使用大 O 表示法表示时会直接将其忽略。

• 例如，某个算法复杂度为 O(n)，至于具体程度是 100n 还是 2n，在大 O 表示法看来是相同的。

这也意味着，采用大 O 表示法可能出现一种情况：

• 带有巨大常量的线性算法，可能会比小常量的指数算法更受欢迎，因为该方法并不会显示真实运行的具体时间。

因此请记住：

大 O 表示法只是某种度量方法，它所显示的算法复杂度，不一定代表真正最佳（最快）的算法。

---

四、复杂度随元素个数变化的对照表

表 2：复杂度随元素个数的变化情况

复杂度种类	大 O 表示	n=1	n=2	n=5	n=10	n=50	n=100	n=1000	n=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	1000	10,000
2 次方阶	O(n²)	1	4	25	100	2500	10,000	1,000,000	100,000,000

从表 2 可见：

• 当算法处理元素较少时，各复杂度差别很小，此时效率的优劣通常由被大 O 表示法忽略的因素决定。
• 当处理元素越多，各复杂度差别越大，被忽略部分变得无关紧要。

因此，在实际考量算法复杂度时，输入量 n（即操作元素个数）的值必须足够大才具有实际意义。