學習 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 （操作元素的個數）的值必須足夠大才有意義。