算法复杂度的衡量标准:大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 (操作元素的个数)的值必须足够大才有意义。