演算法執行時間（algorithmic run time） 與程式的執行時間略有不同。既然演算法只是一個想法，評估它的處理速度沒有上限——所以用分鐘或秒表達演算法執行時間毫無意義。

用輸入大小 n 衡量#

排除處理器速度與架構後，演算法的重要未知數是輸入大小 n。對 1,000 個元素排序當然比對 10 個元素慢。以下簡單演算法：

for(i = 1 to n) {
   Do something;
   Do another thing;
}
Do one last thing;

迴圈跑 n 次、每次做兩個動作，再做最後一個動作，時間複雜度為 2n + 1。若加一層巢狀迴圈，複雜度變成 n² + 2n + 1。

為何只看成長趨勢#

這種細節仍太瑣碎。當 n 變大，2n + 5 與 2n + 365 的相對差異越來越小；但 2n² + 5 與 2n + 5 的相對差異越來越大。演算法執行時間最重要的是這種廣義的成長趨勢。

比較 2n + 365 與 2n² + 5：小 n 時後者較快，n = 30 時打平，之後前者永遠更快。既然只有 30 個 n 值後者較好、卻有無限個 n 值前者較好，2n + 365 一般更有效率。

一般而言，時間複雜度相對輸入大小的成長率，比任何固定輸入的時間複雜度更重要。 這對特定真實應用未必成立，但在所有可能應用上平均後傾向為真。

漸進記法（Big-O）#

漸進記法（asymptotic notation） 表達演算法效率——之所以叫「漸進」，是因為它處理輸入大小趨近無限時的行為。

把時間複雜度轉成大 O 的簡單方法：只看最高次項，因為 n 夠大時它最重要。

• 3n⁴ + 43n³ + 763n + log n + 37 → O(n⁴)
• 54n⁷ + 23n⁴ + 4325 → O(n⁷)