核心概念#
在 Topic 15（估算）中談到了估算走路時間或專案時程。但還有另一種務實程式設計師幾乎每天都在使用的估算：估算演算法消耗的資源——時間、處理器、記憶體等。
這類估算常常至關重要。你知道程式在 1,000 筆記錄下跑得順暢，但擴展到 1,000,000 筆時會怎樣？哪些部分需要最佳化？
答案通常可以透過常識、一些分析，以及一種叫做 Big-O 表示法的近似方法來回答。
Big-O 表示法#
Big-O 表示法是一種處理近似值的數學方法。當我們說某個排序例程對 n 筆記錄排序需要 O(n^2) 時間，我們是說最壞情況下所需時間大約與 n 的平方成正比。輸入數量翻倍，時間大約增為四倍。
Big-O 表示法設定了我們測量的東西的上界。它永遠不會給你實際的數字——它只告訴你這些值如何隨著輸入變化而變化。
Tip 63 - Estimate the Order of Your Algorithms（估算你的演算法的量級）
常見的 Big-O 表示法#
| 表示法 | 類型 | 範例 |
|---|---|---|
| O(1) | 常數 | 陣列元素存取、簡單語句 |
| O(log n) | 對數 | 二分搜尋 |
| O(n) | 線性 | 循序搜尋 |
| O(n log n) | 比線性稍差 | Quicksort、Heapsort 的平均情況 |
| O(n^2) | 平方 | 選擇排序、插入排序 |
| O(n^3) | 立方 | 兩個 n x n 矩陣相乘 |
| O(2^n) | 指數 | 旅行推銷員問題、集合分割 |
常識估算#
你可以用常識估算許多基本演算法的量級：
- 簡單迴圈：從 1 到 n 的簡單迴圈，大概是 O(n)
- 巢狀迴圈：迴圈中套迴圈，變成 O(m x n)，簡單排序演算法如泡沫排序通常是 O(n^2)
- 二分法（Binary chop）：如果演算法每次迭代將考慮的集合減半，大概是 O(log n)
- 分治法（Divide and conquer）：將輸入分成兩半獨立處理再合併結果，如 Quicksort，平均是 O(n log n)
- 組合（Combinatoric）：涉及排列組合時，運行時間可能失控（階乘級）
演算法速度的實務考量#
- 每當你寫簡單迴圈，你知道是 O(n) 演算法；如果迴圈裡還有內層迴圈，就是 O(n^2)。問自己這些值能長到多大
- 如果不確定程式碼要跑多久或用多少記憶體，嘗試運行它——改變輸入大小，畫出結果曲線。三到四個點就能給你概念
- 也要考慮程式碼本身在做什麼。對於較小的 n，簡單的 O(n^2) 迴圈可能比內層迴圈昂貴的 O(n log n) 更快
- 不要忘記實際考量：小資料集上線性增長的程式碼，遇到百萬筆記錄可能因為系統 thrashing 而降級
Tip 64 - Test Your Estimates（測試你的估算）
如果很難取得準確的時間數據，使用 code profiler 來計算演算法中各步驟的執行次數，並對照輸入大小畫圖。
最快不一定最好#
選擇演算法要務實——最快的不一定是最好的。小資料集上，直接的插入排序可能和 Quicksort 一樣快，而且更容易寫和除錯。也要注意演算法的設置成本（setup cost）——小輸入時這些設置可能主宰了運行時間。
警惕過早最佳化（premature optimization）。先確認演算法真的是瓶頸，再投入時間去改進它。
相關章節#
- Topic 15，估算