算法复杂度的衡量标准：大O表示法

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

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

举个例子，当算法运行时间随元素个数成线性增长时（即如果元素个数呈倍数增长，运行时间也呈倍数增长），该算法的复杂度用 O(n) 来表示；反之，如果算法的运行时间和输入量 n 无关，则该算法的复杂度就用 O(1) 来表示。

表 1 列出了常见的算法复杂度种类，以及使用大 O 表示法表示的复杂度。

表 1 常见的算法复杂度表示

算法复杂度种类	含义	大 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 表示法只是某种度量方法，它所显示的算法的最佳复杂度，并不一定就是真正的最佳（最快）算法。

表 2 复杂度随元素个数对照表

复杂度		元素个数
种类	大 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 （操作元素的个数）的值必须足够大才有意义。