大 O 記號
大 O 記號是一種簡潔的速記，用來表示當輸入變大時某樣東西增長得有多快，寫成 O(...)，讀作「……的階」或「大 O 的……」。它是我們說話的語言：「這個演算法是線性的」寫作 O(n)，「這個是平方級的」寫作 O(n^2)，「這個幾乎不怎麼變慢」寫作 O(log n)。最值得養成的一種直覺是：大 O 會忽略細枝末節和常數，只保留當 n 極大時占主導的那一項。想像兩輛車。一輛起步快但有極速上限；另一輛永遠在加速。短距離衝刺第一輛贏，可道路夠長，第二輛總會反超。大 O 關心的就是那條長路——n 無限增大時的行為。
兩條簡單規則就能讓它豁然開朗。第一，丟掉常數因子：3n + 50 就是 O(n)，因為把工作量翻三倍、或加上固定的 50，並不改變曲線的形狀，只改變它的陡峭程度，而陡峭程度是個硬體細節。第二，只保留最大的那一項：n^2 + n + 100 是 O(n^2)，因為一旦 n 變大，n^2 那部分就把其餘一切都比下去了。所以 O(n^2) 並不意味著「恰好 n^2 步」——它意味著「增長不會快過某個常數乘以 n^2」。它是增長率的一個上界，而不是步數。
一條好用的階梯，隨 n 增大從最仁慈到最殘酷：O(1) 常數、O(log n) 對數、O(n) 線性、O(n log n)（好的排序的速度）、O(n^2) 平方、再到 O(2^n) 指數（它會很快變得毫無希望）。別被符號嚇住：大 O 不過是一個關於「如何隨規模放大」的承諾。它故意把小東西扔掉，好讓你能憑兩個演算法的本質性格去比較它們，挑出那個在輸入變大時仍能屹立不倒的。
long long sum = 0; for (int i = 0; i < n; ++i) // loop runs n times sum += a[i]; // O(n) total work, O(1) extra space
把 n 個數求和，做約 n 次加法：O(n) 時間、O(1) 額外空間。
O 是上界（增長不快過）。它的兄弟們：Omega 是下界，Theta 是緊界（上下界同時成立）。日常說話裡，「O」通常指最壞情況的增長。