刷題真正要練的不是「背更多題」，而是兩件可遷移的能力：一套遇到陌生題的拆解流程，以及一雙估得出時間/空間成本的眼睛。前者讓你在白板前不慌、能一步步逼近最佳解；後者讓你在動手前就知道哪個方向值得走。這一章把這兩件事講清楚，後面每個 pattern 章都建立在它之上。
解題七步法
面試時最忌「看到題目直接寫」。先把問題吃透、跑過例子、講清楚暴力解，再開始優化，往往比急著寫更快收斂到正解。
- 聽清楚 (Listen)：抓住每個條件。「已排序」「只含正整數」「會重複呼叫」這類字眼往往就是解法的鑰匙。
- 畫例子 (Draw Example)：手造一個夠大、非特例的例子。太小的例子會誤導，特例（空、全相同）留到測試階段。
- 先寫暴力解 (Brute Force)：講出一個一定對但很慢的解，標出它的複雜度。這是優化的起點，不是恥辱。
- 優化 (Optimize)：用下面的 BUD 框架找瓶頸，逐步改進。
- 走一遍 (Walk Through)：把優化後的想法在腦中或紙上完整跑過一次，確認邏輯再落鍵盤。
- 實作 (Implement)：寫乾淨、模組化的程式。卡住時先用一個命名好的函式佔位，之後再補。
- 測試 (Test)：先看概念性錯誤，再跑特例、邊界、與大輸入。
TIP
「先暴力、再優化」不是浪費時間。暴力解定義了問題的正確性基準，也常常是優化版的退路；BCR（見下）則告訴你優化還有多少空間。
BUD 最佳化框架
拿到一個可運作但太慢的解後，沿三個方向找突破口：
- Bottlenecks（瓶頸）：整體時間被哪一步主導？例如「先排序
O(n log n)再線性掃描」，瓶頸在排序；若掃描那步能容忍未排序輸入，排序就是可砍的目標。 - Unnecessary work（無用功）：是否做了結果用不到的計算？例如找
a^3 + b^3 = c^3 + d^3時，固定a, b, c後d已被唯一決定，不需要第四層迴圈去枚舉。 - Duplicated work（重複功）：同一筆計算是否被反覆執行？把中間結果存進 Hash Map 或前綴陣列，往往能把一層迴圈消掉——這正是 DP 與前綴和的共同核心。
NOTE
三個方向常彼此呼應：消除重複功通常就是打掉瓶頸的手段，而辨識無用功則需要回頭看題目到底要什麼。
BCR：最佳可能複雜度
BCR（Best Conceivable Runtime） 是「光是讀完必要輸入、產生必要輸出」就無法避免的下界，與你目前的解法無關。
- 要回傳陣列中所有配對 → 至少
O(n^2)，因為輸出本身就有n^2量級。 - 要在未排序陣列中找一個值 → 至少
O(n)，因為沒讀完無法確定不存在。
它的用途是喊停：當你的解已達到 BCR，就不必再硬擠優化；若還沒到，BCR 會提示「理論上還有空間」，常見手段是「用空間換時間」或「預處理出有序/索引結構」。
複雜度分析硬知識
| 概念 | 重點 |
|---|---|
| 捨棄常數與非主導項 | O(2n)、O(n + 100) 都是 O(n)；O(n^2 + n) 是 O(n^2)。 |
不同輸入別共用 n | 走訪兩個長度不同的陣列是 O(a + b) 或 O(a * b)，不是 O(n) 或 O(n^2)。 |
| 加法 vs 乘法 | 「做完 A 再做 B」是 O(A + B)；「A 的每一步都做一次 B」是 O(A * B)。 |
O(log n) 的來源 | 每一步把問題規模減半（二分搜尋、平衡樹下降）。 |
| 遞迴的複雜度 | 多分支遞迴約為 O(branches^depth)；費氏數列樸素遞迴是 O(2^n)，記憶化後降到 O(n)。 |
| 遞迴的空間 | 同時存在的呼叫只有一條路徑，空間是 O(depth)，不是節點總數。 |
TIP
攤還分析（amortized）：動態陣列在容量滿時加倍擴容，單次擴容是 O(n)，但把 1 + 2 + 4 + ... + n ≈ 2n 的總成本均攤到 n 次 push，平均每次仍是 O(1)。Hash Map 的「平均 O(1)」也是同理。
back-of-the-envelope 估算
面試與實務都常要在三十秒內估出「這個做法跑得動嗎」。記住幾個錨點就能心算：
2^10 ≈ 10^3：所以2^20 ≈ 10^6、2^30 ≈ 10^9。要判斷O(2^n)會不會爆，看 n 是否超過 30 上下。- 規模直覺：
n ≤ 20可容忍指數/回溯；n ≤ 5000可容忍O(n^2)；n ≤ 10^6需要O(n)或O(n log n)；n ≥ 10^9通常只剩O(log n)或O(1)。 - 一秒約
10^8次簡單運算：拿題目給的資料量乘上你估的複雜度，跟這個數量級比一下就知道會不會逾時。 - 72 法則：成長率 r%（每年）下，數量翻倍約需
72 / r年——估資料成長、容量規劃時好用。
NOTE
估算重點是量級而非精確值。常數因子（快取命中、記憶體連續性）在工程上影響實感，但在判斷「哪個複雜度等級」時可以先忽略。
比較排序的下界
任何「只靠兩兩比較」的排序，最壞情況都不可能快於 O(n log n)：n 個元素有 n! 種排列，要靠比較區分它們，至少需要 log2(n!) ≈ n log n 次比較。
這條下界解釋了為什麼 O(n log n) 排序在許多解法裡是「無法再砍的瓶頸」；也提示：若想更快，就得跳出比較模型，改用計數排序、桶排序、基數排序這類非比較式做法（詳見 Binary Search → 排序與搜尋總覽）。