基礎與複雜度
時間複雜度
時間複雜度回答一個很實用的問題：當輸入變大時，執行時間是怎樣增長的？我們不用碼錶去掐你的程式——那會受你的筆電、所用語言、甚至機器有多忙的影響——而是把演算法執行的基本步驟數，寫成輸入規模（通常記作 n）的一個函數。碼錶上的秒數會因機器而異；增長的「形狀」卻不會。我們在意的正是這個形狀，因為它能預測當 n 是一千、一百萬、十億時會發生什麼。
我們用大 O 記號來描述這個形狀，只保留最主導的那一項，並丟掉常數。掃一遍串列去找最大值，會把每個元素碰一次，所以是 O(n)——線性：輸入翻倍，工作量大致翻倍。把每一對元素都比一遍是 O(n^2)——平方級：輸入翻倍，工作量翻成四倍。二分搜尋每一步把搜尋範圍砍半，所以是 O(log n)——幾乎不怎麼漲。而無論集合多大、耗時都一樣的查找（比如一個好的雜湊表），是 O(1)——常數。
之所以要緊，是因為一筆殘酷的算術。當 n = 1,000,000 時，一個 O(n) 的演算法大約做一百萬步；一個 O(n^2) 的演算法要做一百萬乘一百萬——一兆步——這能把一項一秒的任務變成跑上好幾天的任務。所以一個謹慎的程式設計師對一個演算法問的第一個問題，不是「它能用嗎？」，而是「它的時間是怎麼隨規模放大的？」。我們通常報告最壞情況（在規模為 n 的所有輸入裡演算法最慢能慢到什麼程度），因為那是你能依賴的保證；不過平均情況分析和攤還分析會把故事的其餘部分講完。
int pairs = 0;
for (int i = 0; i < n; ++i) // runs n times
for (int j = i + 1; j < n; ++j) // ~n times each
if (a[i] == a[j]) ++pairs; // O(n^2) comparisons total對 n 個元素的兩層巢狀迴圈，做的比較數量在 n^2 量級——平方時間。
又稱
另見