Phase 03 — Algorithms（Day 21–30）

What：Big-O 描述一個演算法所需的資源（時間或空間）隨輸入規模 n成長時的成長趨勢——只保留成長最快的那一項、丟掉常數與低階項。O(2n + 100) 寫成 O(n)，因為當 n 夠大時，+100 這個常數與 2這個係數對「趨勢」的影響可以忽略，重要的是「輸入變兩倍，成本大概變兩倍」這件事本身。

• O(1)——常數時間，操作次數不隨 n 改變。例：array 用 index 存取（base + k*size 直接算出位置，見 Day 11）、hash map 平均情況的 get/put（見 Day 12：計算 hash 值、跳到對應 bucket，這兩步都不隨 n 增加而變多）。
• O(log n)——每一步都把問題規模砍掉一個固定比例（通常是一半）。例：binary search 每比較一次，搜索範圍就減半，n 筆資料最多只需要log₂n 次比較就能縮到剩 1 筆——n = 1,000,000 只需要約 20 次。平衡二元樹（Day 18）的 search/insert/delete 也是 O(log n)，理由相同：每往下一層，還沒探索的節點數量減半。
• O(n)——操作次數與 n 成正比，通常是走訪一次全部資料，不會重複走訪同一筆。例：在未排序陣列裡找最大值，必須每個元素都看過一次，不能跳過任何一個。
• O(n log n)——對 n 筆資料，每筆資料都要付出 O(log n) 的成本，或是把問題切成 log n 層、每層要處理全部 n 筆。例：merge sort 把陣列切成 log n 層（每層都是切一半），每層都要花 O(n) 把資料合併回去，總成本 O(n) × O(log n) = O(n log n)（Day 25 會展開）。
• O(n²)——對 n 筆資料中的每一筆，都要再走訪一次其餘的 n 筆。最典型的寫法是雙層巢狀迴圈跑過同一個集合：外層跑 n 次，內層對每個外層元素再跑 n 次，總共 n × n = n² 次操作。例：naive 重複偵測（雙層迴圈比對每一對元素是否相同）。

Space Complexity：跟時間複雜度用同一套記號，但量的是「額外需要的記憶體」，不包含輸入本身占用的空間。要注意兩個容易漏算的地方：(1) recursion 的 call stack——每多一層遞迴呼叫就多佔一份 stack frame，遞迴深度為 d 時 space complexity 至少 O(d)，即使函式本身沒有配置任何額外資料結構；(2) 回傳值如果是「新配置的資料結構」（例如回傳一個新陣列而不是原地修改），那份回傳值也要算進 space complexity，除非題目明確說「不計入輸出所需的空間」。

Amortized Complexity（攤銷複雜度）：某個操作大部分時候很便宜，但偶爾會觸發一次昂貴的操作，把這個昂貴操作的成本平均攤到所有操作上，得到的長期平均成本。Day 11 動態陣列的 append 是最標準的例子：多數 append 是 O(1)（capacity 還夠用，直接寫入），但每次 capacity 用滿時觸發的 resize 是 O(n)（要配置新陣列並複製全部元素）；因為 resize 的頻率隨 n 遞減（capacity 每次翻倍），把 n 次 append 中所有 resize 的複製成本加總、除以 n，平均每次操作只分攤到O(1)。攤銷 O(1) 不等於「每次都是 O(1)」——這正是下面 Failure mode 要強調的地方。

Failure Modes：

1. 誤判「巢狀」一定是 O(n²)：巢狀迴圈的複雜度取決於兩層各自的範圍，不是「有巢狀就是平方」。外層跑 n 次、內層固定跑 k次（k 不隨 n 變化）是 O(n·k) = O(n)；外層跑 n 次、內層跑m 次（m 是另一個獨立集合的大小）是 O(n·m)，不是 O(n)也不是 O(n²)。
2. 誤判 hash map/set 操作一定是 O(1)：這是平均情況（好的 hash function、低碰撞率），最差情況（大量 hash 碰撞、退化成 linked list 走訪）是 O(n)。如果一個迴圈裡對同一個 hash set 做n 次操作，平均情況總成本 O(n)，但如果 hash function 設計得差、或攻擊者能刻意製造碰撞（hash flooding），總成本可能退化到 O(n²)。
3. 把攤銷成本當成保證的單次成本：見過某次 append 花了明顯比其他幾百次都久的時間，誤以為「這個函式效能不穩定」，但如果是攤銷 O(1) 的資料結構（動態陣列、Go 的 map），這種偶發的尖峰是設計上預期的行為，不是 bug；但如果這個尖峰發生在延遲敏感的路徑上（例如 API request 的 hot path），攤銷 O(1) 仍然可能造成使用者能感受到的 p99 延遲尖峰——這時該優化的不是「平均值」，而是「最差單次成本」，見下方 Backend 段落。
4. 在迴圈內對 list/slice 呼叫 contains/in：list 或未排序slice 的成員檢查是 O(n)，如果這行程式碼被包在一個跑 n 次的迴圈裡，整段程式碼就從「看起來像 O(n)」的迴圈變成實際 O(n²)——這是 code review 最常漏掉的複雜度陷阱之一，因為兩個 O(n) 「疊」在一起很容易被略讀成「反正都是 O(n)」。

Backend Applications：

• N+1 query 問題：對 n 筆父資料，逐一各發一次 query 抓子資料，總共 n+1 次資料庫往返（round trip），是 O(n) 次網路 I/O；用一次JOIN 或一次 WHERE id IN (...) 批次查詢可以把它降到 O(1)次往返（查詢本身的資料庫端成本另計）。這是複雜度分析在 Backend 最常見的實戰場景——差異不是「演算法複雜度」而是「I/O 次數」，但分析方法完全相同：找出隨 n 成長的操作、算出成長趨勢。
• p99 延遲尖峰排查：上面 Failure mode 第 3 點提到的攤銷成本尖峰，在真實系統中常表現為「平均延遲很低，但 p99/p999 延遲遠高於平均」。排查時如果懷疑是攤銷操作造成，可以檢查是否有動態陣列 resize、hash map rehash、連線池動態擴充等「平常 O(1)、偶爾 O(n)」的操作發生在 request 處理路徑上，並考慮預先配置足夠容量來消除這類尖峰（Day 11 已示範過 slice 預先分配容量的做法）。
• 分頁 OFFSET 陷阱：SELECT * FROM t ORDER BY id LIMIT 20 OFFSET 100000 表面上看起來是常數時間的分頁，但多數資料庫實作仍要先數過（或掃過）前 OFFSET 筆再開始回傳，等同 O(offset) 而不是 O(1)，offset 越大越慢——這是「複雜度直覺被 SQL 語法包裝掉」的典型例子，Day 31+（Phase 04 Database Internals）會從 B-Tree 結構的角度解釋為什麼。

``text func process(records []Record) []string {seen := make(map[string]bool)var result []string for _, r := range records { // (A)key := computeKey(r) // O(1)，純字串組合 if !seen[key] { // (B)seen[key] = true // (C)merged := mergeWithExisting(result, r) // (D) 見下方說明 result = merged}}return result}``

其中 mergeWithExisting(result, r) 的實作是：走訪目前的 result（長度最多與 records 同長，設為 m），找出是否有語意相同的項目可以合併，若有就地更新、若無就 append，本身是 O(m) 操作。不能直接看答案，先自己推導：(A) 是一層 O(n) 迴圈；(B)(C) 是 hash map 操作，平均 O(1)；(D) 每次呼叫是 O(m)，而 m（result 目前長度）最壞情況下會跟著迴圈次數一起成長到接近 n。把 (D) 攤在 (A) 的 n次迴圈裡，最壞情況總成本是 O(1) + O(2) + O(3) + ... + O(n) =O(n²)——即使程式碼裡完全沒有寫出巢狀迴圈的語法（mergeWithExisting的迴圈被包在函式呼叫裡），複雜度依然是 O(n²)，瓶頸在 (D)。改善方式：如果「合併」的判斷條件可以轉換成 key 查找（例如用另一個 hash map 記錄「語意 key → result 裡的位置」），(D) 可以降到平均 O(1)，整體降到 O(n)。

What：用兩個指標（索引）同時走訪一個資料結構（通常是排序後的陣列或字串），依據某個條件決定指標往哪個方向移動，取代原本需要巢狀迴圈才能列舉的「所有配對」。

• 對向雙指標（opposite-direction）：left 從頭開始、right從尾開始，往中間逼近。典型應用：在已排序陣列中找「和等於 target 的一對數字」——比較 nums[left]+nums[right] 與target：太小就 left++（換更大的值，增加和）、太大就right--（換更小的值，減少和）、相等就找到答案。每一步都讓left 與 right 的距離縮短 1，最多跑 n 步，left 永遠不會超過 right，覆蓋所有「不會被排除」的配對。
• 同向雙指標／快慢指標（fast-slow）：兩個指標從同一端出發，以不同速度或不同觸發條件前進。典型應用一：原地移除/去重（slow 指向「下一個要寫入的位置」，fast 逐一檢查每個元素，符合條件才把 fast 位置的值寫到 slow 再讓 slow++）；典型應用二：Linked List 判斷是否有環（Floyd's Cycle Detection，slow 每次走一步、fast 每次走兩步，如果鏈表有環，fast 最終一定會追上 slow；如果沒有環，fast 會先走到 nil）——這個應用不需要排序，靠的是「速度差」這個單調遞增的相對位移，而不是數值大小的單調性。

Failure Modes：

1. 在未排序資料上直接套對向雙指標：對向雙指標的正確性建立在「排序後移動指標的方向必然朝正確方向逼近」這個單調性上；資料沒排序時，nums[left]+nums[right] 太大不代表換更小索引的right 一定能修正，會漏掉正確答案。
2. 移動指標的條件寫反：對向雙指標最常見的錯誤是「和太大時卻移動 left」（應該移動 right 讓和變小）；同向雙指標最常見的錯誤是快慢指標的觸發條件寫成 fast == slow（在起點就相等，迴圈根本不會執行）而不是先移動再比較。
3. 邊界條件 left == right 或 left > right 沒有正確處理：對向雙指標的迴圈條件通常是 left < right（找「一對」不同位置的元素）而不是 left <= right，如果題目要求「同一個元素能不能用兩次」沒看清楚，容易在邊界多算或漏算一種情況。

Backend Applications：日誌／事件串流的「去重後寫入」常用同向雙指標的原地去重模式（slow/fast）避免額外配置一份新陣列；Rate limiter 的滑動視窗計數（下一天 Sliding Window 會展開）本質上也是一種同向雙指標，只是移動條件從「數值大小」換成「時間戳記」。

What：用一對指標 left/right 維護一個連續的「視窗」（子陣列或子字串），right 負責擴張視窗、left 負責收縮視窗，視窗內維護一份隨內容增減增量更新的統計量（總和、字元計數、相異元素個數等），避免每次都重新掃描整個視窗來計算這份統計量。

• 固定大小視窗：視窗大小 k 固定，right 每前進一步，left就跟著前進一步（right - left + 1 == k 這個不變量全程維持）。典型應用：「大小為 k 的子陣列最大總和」——維護視窗內總和，right 前進時加上 nums[right]，同時 left 前進時減去nums[left]，每一步都是 O(1) 更新，全程 O(n)。
• 可變大小視窗：right 一路前進以擴張視窗，直到視窗「違反」某個條件（或反過來，「滿足」某個條件），這時讓 left 前進以收縮視窗，直到視窗重新符合要求，如此反覆。典型應用：「不含重複字元的最長子字串」——right 前進時把新字元加進一個統計「視窗內字元出現次數」的 hash map，只要目前字元的計數變成 2（代表視窗內有重複），就持續讓 left 前進、把 left 指向的字元計數減 1，直到重複的字元計數重新降回 1；每一步都用視窗當前的長度（right-left+1）更新答案。關鍵不變量：right 從頭到尾只會前進 n 次，left 從頭到尾也只會前進最多 n 次（left 永遠不會超過 right 之後又回頭），所以即使外層迴圈與內層收縮迴圈「看起來」是巢狀結構，兩個指標合計的移動次數是 O(n)，不是 O(n²)——這是初學者最容易誤判複雜度的地方，見下方 Failure mode。

Failure Modes：

1. 誤判雙指標巢狀迴圈是 O(n²)：可變大小視窗的程式碼經常寫成for right := range nums { for 視窗不合法 { left++ } } 這種「看起來像巢狀迴圈」的結構，初學者容易直接判定為 O(n²)。正確判斷方式是看每個指標各自總共移動了多少次，而不是看迴圈的巢狀層數——left 與 right 全程單調遞增、各自最多移動 n次，兩者相加是 O(n)，不是 O(n) × O(n)。
2. 忘記在收縮視窗時同步更新統計量：left 前進、元素離開視窗時，如果忘記把該元素從統計量（hash map 計數、視窗總和等）中移除，會導致後續的判斷條件用到「已經不在視窗內」的過期資訊，產生錯誤答案且不易察覺（因為程式不會 crash，只是結果數字不對）。
3. 固定大小視窗誤用可變大小視窗的收縮邏輯：固定視窗應該是right 前進一步、left 也跟著前進一步（維持大小恆定），如果誤用「視窗不合法才收縮」的可變邏輯，會導致視窗大小不受控制地變化。

Backend Applications：Rate limiting 的「滑動視窗計數」（sliding window counter）是這個 pattern 在系統設計上最直接的應用——維護「過去 N 秒內的請求數」而不是每次請求都重新掃描全部歷史紀錄，right 對應新進來的請求、left 對應「超過時間視窗因而該被排除」的舊請求；即時監控系統計算「過去 5 分鐘的平均延遲/錯誤率」也是同樣的結構，用增量更新（新資料進來加、舊資料出視窗減）取代每次重新掃描整個時間窗口的資料。

What：Binary Search 是一種利用單調性（monotonicity）把搜索範圍每次砍半的演算法——不限於「在排序陣列裡找數字」，只要能定義一個搜索空間，以及一個在該空間上「單調」的判斷函式（predicate：給定一個候選值，回答 true/false，且這個 true/false 沿著搜索空間移動時只會翻轉一次，不會忽 true 忽 false），就能用 Binary Search 找到判斷函式翻轉的那個邊界點。

Mechanism（依 acceptance 要求逐一展開）：

• 標準 Binary Search（找目標值本身）：low, high := 0, len(nums)-1；迴圈中 mid := low + (high-low)/2（用這個寫法而不是(low+high)/2，避免 low+high 在極端情況下整數溢位）；若nums[mid] == target 回傳 mid；若 nums[mid] < target，代表target 若存在必定在右半邊，low = mid+1；否則 high = mid-1；迴圈條件 low <= high，跳出迴圈仍未命中代表不存在。

• Lower Bound（第一個 ≥ target 的位置）：語意是「target如果要插入這個排序陣列、同時保持陣列有序，最靠左可以插入的位置」——等同標準函式庫的 lower_bound（C++）、bisect_left（Python）。實作：low, high := 0, len(nums)（注意 high 是len(nums) 不是 len(nums)-1，因為答案可能是「插在陣列最後面」）；迴圈條件 low < high；mid := low + (high-low)/2；若nums[mid] < target，代表 mid 連同它左邊都不可能是答案，low = mid+1；否則（nums[mid] >= target）mid 有可能是答案（或答案在它左邊），high = mid；迴圈結束時 low == high，就是答案。

• Upper Bound（第一個 > target 的位置）：與 Lower Bound 幾乎相同，只把判斷條件的 < 改成 <=——若 nums[mid] <= target，low = mid+1；否則 high = mid。Lower Bound 與 Upper Bound 的差，正好是 target 在陣列中出現的次數（upperBound -lowerBound），這是「在排序陣列中找某個值出現次數」的標準做法，不需要真的線性掃描。

• Search Space（搜索空間）：Binary Search 不需要作用在「一個陣列的索引」上——它可以作用在任何具備單調性的抽象數值範圍上。例如：在一個「答案介於 1 到 10^9 之間、且答案越大某個條件越容易滿足（或越難滿足）」的問題裡，low/high 可以直接設成「可能的答案的最小值/最大值」，而不是陣列的索引 0 到len-1——這是 Search Space 這個詞的意思：搜索的對象是「答案本身的值域」，不是資料結構裡的位置。

• Binary Search on Answer：當一個問題問「求最小的 X 使得某條件成立」（或「求最大的 X 使得某條件成立」），而這個條件對 X 具備單調性（X 越大條件越容易滿足，或越大越難滿足），就可以對 X 的值域做 Binary Search，而不需要、也通常無法直接推導出解析解。流程：(1) 確定 X 的合理範圍 [low, high]；(2) 寫一個canAchieve(x) bool 判斷函式，驗證「X = x 時條件是否成立」；(3) 對 [low, high] 做 Binary Search，每次用 canAchieve(mid)決定往哪一半收斂。判斷函式必須是單調的，這是能不能用這個技巧的先決條件——如果條件對 X 不是單調（例如條件時而成立時而不成立、沒有固定的翻轉點），Binary Search on Answer 會得到錯誤答案，這也是它最常被誤用的地方。

Failure Modes：

1. mid 計算用 (low+high)/2 造成整數溢位：在允許索引/數值範圍極大的語言（如固定寬度整數的 Go int32）中，low+high可能超過該型別能表示的最大值而溢位，正確寫法是mid := low + (high-low)/2。
2. Lower/Upper Bound 的邊界寫錯，high 用成 len(nums)-1：Lower/Upper Bound 的答案可能是「插入在陣列最後面」（索引等於len(nums)），如果 high 初始化成 len(nums)-1，會漏掉這個合法答案。
3. Binary Search on Answer 用在非單調的判斷函式上：這是最容易犯的概念性錯誤——沒有先驗證「條件是否真的單調」就直接套用模板，得到的答案可能剛好落在某個局部符合條件、但不是真正邊界的位置。使用這個技巧前，必須先能口頭證明「X 越大（或越小）條件越容易成立」，證不出來就不能用。
4. 迴圈不變量與收斂條件不一致：標準 Binary Search 用low <= high 搭配 mid±1 收斂；Lower/Upper Bound 用 low < high搭配 high = mid（不是 mid-1）收斂——兩種模板混用（例如low < high 卻寫 high = mid-1）會導致漏掉邊界值或無窮迴圈。

Backend Applications：資料庫索引本身的查找（Day 31+ B-Tree 會展開）是 Binary Search 思想在儲存層的體現；API 限流/資源分配問題常見「求滿足 SLA 的最小資源配置量」，這正是 Binary Search on Answer 的典型場景（見下方陌生題）；版本控制系統的 git bisect（用二分法在一串 commit 中找出第一個引入 bug 的版本）是 Lower Bound 思想在「commit 歷史」這個搜索空間上的應用——canAchieve(commit) 對應「這個 commit 是否還沒有 bug」這個單調判斷（假設 bug 引入後所有之後的 commit 都有這個 bug）。

陌生題（Core Fundamentals 要求）：某個批次匯入服務要把 n 份檔案分配給固定數量的 k 台 worker 平行處理，每份檔案有各自的處理秒數 cost[i]，檔案不能被拆開、必須整份交給同一台 worker，worker 之間也不能事後搬移工作。要在不重新設計架構的前提下，決定一種分配方式，使得「最慢的那台 worker 的總耗時」盡量小（這樣整批匯入才能盡快全部完成）。不能直接寫 code，先回答：

為什麼這是一個 Binary Search on Answer 問題？

推導：直接窮舉所有分配方式是指數級的（每份檔案有 k 種去處，k^n 種分配方式），不可行。但注意問題其實是在問「最小化最大值」——如果我們換個角度，去猜「最慢 worker 的總耗時上限 X 最小可以是多少」：給定任意一個候選 X，可以用貪婪法在 O(n) 時間內驗證「X 是否可行」——依序把檔案分給目前的 worker，累積耗時一旦超過 X 就換下一台 worker，最後檢查用到的 worker 數量是否 ≤ k。這個「canAchieve(X)」判斷函式對 X 具備單調性：X 越大，越容易用更少的 worker 做到（因為每台 worker 能扛的耗時上限變大），X 越小則越難（甚至可能需要超過k 台 worker 才裝得下）——單調性成立，滿足 Binary Search on Answer 的前提。low 設為 max(cost[i])（至少要能裝下耗時最長的單一檔案，否則怎麼分都會有一台 worker 超過 X）、high 設為sum(cost[i])（全部檔案都給同一台 worker 的耗時，一定可行），對[low, high] 做 Binary Search，每次用 canAchieve(mid) 決定收斂方向，最終收斂到的 low（此時 low == high）就是最小可行的 X。

再寫 code：實作 canAchieve(cost []int, k int, x int) bool（貪婪分配驗證）與外層 Binary Search，對測資cost = [7,2,5,10,8], k = 2 驗證答案為 18（一種可行分配：[7,2,5] 給 worker A 耗時 14、[10,8] 給 worker B 耗時 18；驗證 17 以下不可行、18 可行）。

What：把一組資料依某個比較規則排成有序序列。依「是否透過兩兩比較決定順序」可分成比較排序（comparison-based，如 merge/quick/heap sort）與非比較排序（如 counting sort、radix sort，靠資料本身的數值特性直接決定位置，不透過比較）。

• O(n²) 比較排序（以 Insertion Sort 為代表）：維護「陣列前半部已排序」的不變量，每次把下一個未排序元素往前插入到正確位置——從右往左逐一比較並搬移比它大的元素，直到找到插入點。最差情況（逆序輸入）每次插入都要搬移前面全部元素，O(n²)；但對「幾乎已排序」的資料非常快（每次插入只需搬移極少元素），這是它在n 很小或資料局部有序時，實務上有時比 O(n log n) 排序更快的原因（多數標準函式庫的排序在小規模子陣列會切換成 insertion sort，正是利用這個特性）。
• O(n log n) 比較排序：Merge Sort：把陣列從中間切一半，遞迴排序左右兩半，再把兩個已排序的子陣列合併（merge）成一個有序陣列——合併時用兩個指標各自指向兩個子陣列的開頭，每次取較小的那個放進結果，指標前進，是 O(m+n) 操作（m、n 為兩子陣列長度）。遞迴切一半共 log n 層，每層所有合併操作加總都是 O(n)，總成本O(n log n)。穩定（相等元素的相對順序不會改變，因為合併時「相等就取左邊那個」）；額外空間 O(n)（合併需要暫存空間，不是原地排序）。
• O(n log n) 比較排序：Quick Sort：選一個 pivot，把陣列 partition 成「比 pivot 小」與「比 pivot 大」兩部分（pivot 落在正確的最終位置），再遞迴排序兩部分。平均情況下（pivot 選得夠隨機）每次 partition 大致把陣列切成兩半，O(n log n)；最差情況（pivot 總是選到最小值或最大值，例如對已排序陣列固定選第一個當 pivot）退化成 O(n²)（每次只切掉一個元素）。原地排序，額外空間 O(log n)（遞迴 call stack）。不穩定（partition 過程中相等元素的相對順序可能被打亂）。
• 非比較排序：Counting Sort：如果資料的值域已知且不大（例如 0～k 的整數），可以不透過比較，直接統計每個值出現的次數，再依值的大小依序輸出——時間複雜度 O(n+k)，當 k 是常數或遠小於n log n 時比任何比較排序都快。代價：只適用於離散、值域有限的資料（無法對任意可比較物件排序），且空間複雜度 O(k)，k 很大時不划算。

Stability（穩定性）：排序後，原本相等的元素是否維持原本的相對順序。多數比較排序演算法本身可以設計成穩定（merge sort 天生穩定；quick sort 天生不穩定，除非額外處理），標準函式庫通常會標明其排序是否穩定（例如 Python sorted/list.sort 保證穩定，Gosort.Slice 不保證穩定、需要用 sort.SliceStable）。

Failure Modes：

1. 需要穩定排序卻用了不穩定的排序函式：多欄位排序（例如先按部門排序、同部門內再按姓名排序）如果分兩次排序（先排姓名、再排部門），必須第二次排序是穩定的，否則同部門內的姓名順序會被打亂——這是實務上很容易忽略、且不會報錯（只是結果「看起來」排序正確，但細看會發現次要排序鍵的順序是錯的）的 bug。
2. 對已排序或近乎排序的資料選錯演算法：對已排序資料使用固定選第一個元素當 pivot 的 quick sort 實作，會直接觸發 O(n²) 最差情況——這也是為什麼許多標準函式庫改用「隨機選 pivot」或「median-of-three」來避免這個已知的攻擊/退化情境。
3. 誤用非比較排序在不符合前提的資料上：對浮點數、字串或值域極大的整數套用 counting sort，會導致 k（值域大小）遠大於n，空間與時間都比比較排序更差，完全喪失非比較排序的優勢。

Backend Applications：資料庫的 ORDER BY 執行計畫在資料量小到能放進記憶體時通常用 quick sort/merge sort 的變體（Day 31+ 會展開EXPLAIN 如何顯示排序策略），資料量大到放不進記憶體則用external merge sort（分批排序後合併，merge sort 的「合併」機制天生適合處理超過記憶體容量的資料，這也是為什麼合併排序在資料庫與大數據系統中比 quick sort 更常被選用，即使平均情況比 quick sort 慢）；日誌系統依時間戳記排序輸出時，若日誌來源本身已經是局部有序（多個 producer 各自時間遞增），用 merge 的思路合併多個有序串流，會比對全部日誌重新排序快得多。

What：遞迴是一個函式在自己的定義裡呼叫自己，把一個問題拆成「規模更小、結構相同」的子問題，直到抵達一個可以直接回答、不需要再拆的最小情況（base case），再把子問題的答案逐層組裝回原問題的答案。

``text factorial(4)→ 呼叫 factorial(3)（frame: n=4，等待回傳值後要乘以 4）→ 呼叫 factorial(2)（frame: n=3，等待回傳值後要乘以 3）→ 呼叫 factorial(1)（frame: n=2，等待回傳值後要乘以 2）→ 呼叫 factorial(0)（frame: n=1，等待回傳值後要乘以 1）→ factorial(0) 命中 base case，直接回傳 1← factorial(1) = 1 * 1 = 1，回傳給上一層← factorial(2) = 2 * 1 = 2，回傳給上一層← factorial(3) = 3 * 2 = 6，回傳給上一層← factorial(4) = 4 * 6 = 24，回傳給呼叫者``

「往下呼叫」的過程（call stack 從 1 層長到 5 層）與「往上回傳」的過程（call stack 從 5 層縮回 1 層）是遞迴唯一的兩個動作——base case 是唯一不再往下呼叫、只往上回傳的那一層，缺少它會導致遞迴永遠不會停止往下呼叫，直到 call stack 用盡記憶體、丟出 stack overflow。

Failure Modes：

1. Base case 缺漏或條件寫錯：例如把 factorial(0) = 1 誤寫成只處理 n == 1，呼叫 factorial(0) 時會不斷遞減到負數、永遠碰不到 base case，最終 stack overflow；base case 必須涵蓋所有「不能再往下拆」的輸入，不是只涵蓋「常見」的那個。
2. 重複子問題沒有被發覺，導致指數級重複計算：naive 遞迴版本的費氏數列 fib(n) = fib(n-1) + fib(n-2) 看似簡單，但 fib(n-2)會在計算 fib(n-1) 的過程中被重複算一次——展開整棵呼叫樹會發現 fib(30) 呼叫了超過兩百萬次函式，時間複雜度是 O(2^n)，即使每次呼叫本身只做一次加法。這個問題不是遞迴本身的錯，而是沒有意識到子問題重疊；Day 29 的 Dynamic Programming 就是用一張表把這些重複計算記下來，直接把 O(2^n) 壓到 O(n)。
3. 每次呼叫都重新配置資料結構，忘記傳遞可重用的參照：例如遞迴組合字串時每層都用 + 產生新字串而不是傳遞可變的 buffer，會讓每層多付出一次複製成本，深度為 d 時額外多花 O(d) 甚至 O(d²) 的隱藏成本。

Backend Applications：Recursive descent parser（遞迴下降剖析器）是解析 JSON、SQL、程式語言語法最常見的實作方式——每個文法規則對應一個函式，規則裡引用其他規則就直接呼叫對應函式，文法本身的巢狀結構（例如 JSON 物件裡可以再放物件）自然對應到函式呼叫的巢狀；檔案系統或巢狀分類（category tree）的走訪（例如計算一個目錄底下所有檔案總大小，含子目錄）用遞迴寫最直觀；GraphQL resolver 對巢狀欄位的解析、protobuf/JSON 深層巢狀結構的序列化與反序列化，本質上都是同一套「遇到巢狀結構就遞迴處理子結構」的思路。

陌生題（Core Fundamentals 要求）：實作一個函式myPow(x float64, n int) float64，計算 x 的 n 次方（n 可以是負數，代表 1/x^(-n)）。不能直接寫 code，先回答：

為什麼單純遞迴呼叫 x * myPow(x, n-1) 是不夠好的解法？更好的做法是什麼？

推導：x * myPow(x, n-1) 每次只把 n 減 1，遞迴深度是 n，時間複雜度 O(n)——雖然正確，但沒有用到「乘法可以合併」這個結構。觀察 x^n：如果 n 是偶數，x^n = (x^(n/2))^2，只需要算一次x^(n/2) 再平方，把問題規模直接砍半；如果 n 是奇數，x^n = x * (x^(n/2))^2（用整數除法，n/2 向下取整）。這是分治（Divide and Conquer）的思路——遞迴，但每次遞迴呼叫都把規模砍成一半而不是減 1，遞迴深度變成 O(log n)，每層只做常數次乘法，總時間複雜度降到 O(log n)。負數次方則是先算 myPow(x, -n) 再取倒數，並注意 n 為 math.MinInt 這種邊界（負數取反會溢位，需要用int64 或先處理特例）。

再寫 code：實作上述「快速冪」（fast exponentiation）遞迴版本，對 myPow(2.0, 10)（答案 1024.0）與 myPow(2.0, -2)（答案0.25）驗證。

What：從一個起點出發，沿著一條路徑盡量往深處走，直到走不下去（碰到底、或所有鄰居都走過）才「回溯」（backtrack）到上一個節點，改走其他還沒走過的分支，直到所有可達節點都被訪問過。

``text func dfs(node, visited) {if node == nil || visited[node] { return }visited[node] = true process(node) // 依題目定義的「處理」for neighbor in node.neighbors {dfs(neighbor, visited)}}``

遞迴呼叫本身就是在用 call stack 當作 DFS 需要的「後進先出」順序——遞迴呼叫 dfs(neighbor) 時，目前的 node 暫停在原地（stack frame 還在），等 neighbor 這整條分支完全走完（它自己以及它所有子孫都訪問過）才回到 node，換下一個 neighbor。也可以不用遞迴、改用顯式 stack（Phase 02 Day 15）手動模擬同樣的「後進先出」順序，兩者在走訪順序上等價，差異只在遞迴用的是 call stack（隱式）、迭代版用的是自己配置的 stack（顯式，能避免遞迴深度過深時的 stack overflow）。

Failure Modes：

1. 對圖（尤其是含環的圖）忘記標記 visited，導致無窮遞迴：樹不需要 visited 是因為樹沒有環、也沒有指向同一個子節點的多條路徑；圖裡任兩個節點可能互相連結（甚至自環），沒有 visited 集合會讓 DFS 對同一個節點重複遞迴下去，永遠不會終止或造成 stack overflow。
2. 誤以為 DFS 找到的路徑一定最短：DFS 只保證「找到一條存在的路徑」，不保證是邊數最少的路徑——如果題目要求最短路徑（邊數），必須用 BFS，不是 DFS 加一個「記錄目前最短」就能等價於 BFS 的行為（因為 DFS 會先把某條可能很長的路徑走到底才回頭比較，浪費大量不必要的探索）。

Backend Applications：依賴解析（例如 Go module 的依賴圖、任務排程系統的 task DAG）用 DFS 判斷是否存在循環依賴（見 Day 30 拓樸排序）；檔案系統遞迴走訪（列出某個目錄底下所有檔案，含所有子目錄）本質上就是對「目錄樹」做 DFS；垃圾回收（garbage collection）演算法中的 mark-and-sweep，「mark」階段從 root 物件出發，沿著參照關係走訪所有還在被使用的物件，正是圖上的 DFS/BFS（依實作而定）。

練習（DFS）：解 LeetCode 200 — Number of Islands（給一個由'1'（陸地）與 '0'（海洋）組成的二維網格，計算島嶼數量，相鄰的陸地上下左右相連算同一座島）。對每個還沒訪問過的 '1'，從它出發做 DFS（flood fill），把整座相連的島全部標記成已訪問，島嶼數量加一；繼續掃描網格直到所有格子都處理過。用

``text grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]``

驗證答案為 3。

What：從一個起點出發，先訪問所有「距離起點一步」的節點，再訪問所有「距離起點兩步」的節點，依此類推，一層一層往外擴散，直到所有可達節點都被訪問過。

``text func bfs(start) {queue := [start]visited := {start: true}distance := {start: 0}for len(queue) > 0 {node := queue.popFront()for neighbor in node.neighbors {if !visited[neighbor] {visited[neighbor] = true distance[neighbor] = distance[node] + 1 queue.pushBack(neighbor)}}}return distance}``

關鍵細節：visited 必須在「加入 queue 的當下」就標記，而不是等到「從 queue 取出處理時」才標記——如果延遲標記，同一個節點可能在還沒被處理前就被其他節點的鄰居掃描到、重複加入 queue 好幾次，不只浪費空間，也可能讓 distance 被錯誤地多次覆寫。

Failure Modes：

1. 對加權圖直接套用 BFS 求「最短路徑」：BFS 的「最短路徑」定義是邊數最少，如果每條邊有不同權重（例如道路長度、任務耗時），邊數最少不等於總權重最小，此時需要 Dijkstra（Day 30 會展開，本質是把 BFS 的 queue 換成依權重排序的 priority queue）。
2. 忘記記錄「怎麼走到這裡」導致無法還原路徑：只求最短距離時上面的 distance map 就夠，但若題目要求印出實際路徑，必須額外維護一個 parent map（記錄每個節點是從哪個節點擴散過來的），走訪結束後從終點沿著 parent 往回追溯到起點。

Backend Applications：網路拓樸中「兩台機器之間最少要經過幾個 hop」的分析、社群網路「兩個使用者之間的最短關係鏈（例如 LinkedIn 的『2 度人脈』）」都是無權重圖上的 BFS 最短路徑；分散式系統的服務探索（service discovery）在拓樸圖上找「離某個節點最近的可用副本」也是同樣的模式；Day 30 的拓樸排序有一個 BFS 版本（Kahn's algorithm），常用於任務排程系統決定「哪些任務可以先平行執行」。

練習（BFS）：解 LeetCode 994 — Rotting Oranges（給一個網格，2 代表腐爛的橘子、1 代表新鮮橘子、0 代表空格，每一分鐘腐爛橘子會讓上下左右相鄰的新鮮橘子也腐爛，求讓所有橘子腐爛需要幾分鐘，若無法讓所有橘子腐爛回傳 -1）。把所有初始腐爛橘子同時加入 queue（多起點 BFS），每一輪（一分鐘）處理 queue 裡目前所有節點、讓相鄰新鮮橘子腐爛並加入下一輪，走過的輪數就是答案；最後檢查網格是否還有新鮮橘子殘留（代表無法到達）。用grid = [[2,1,1],[1,1,0],[0,1,1]] 驗證答案為 4。

What：Backtracking 是在 DFS 的骨架上，加入「在每個節點做一個選擇、往下探索、如果這條路走不通（或已經走完）就撤銷這個選擇、換下一個選擇」的行為，用來窮舉所有滿足條件的組合/排列/子集合，同時能在確定某個分支不可能產生合法解時提早放棄（剪枝），不必把整棵決策樹走完。

``text func backtrack(path, choices) {if isComplete(path) {result.append(copy(path)) // 必須複製，見下方 Failure Mode return}for choice in choices {if !isValid(choice, path) { // 剪枝：提早放棄不合法的分支 continue}path.append(choice) // 選擇 backtrack(path, remainingChoices(choices, choice)) // 探索 path.removeLast() // 撤銷選擇}}``

這正是 DFS（Day 27）的骨架，差別在於多了「選擇/撤銷」這一對配對動作，且每個節點代表「目前為止的部分解」而不是「圖上的一個既有節點」——決策樹是動態生成的，每往下一層就是「多做一個選擇」，回到上一層前必須把這個選擇造成的狀態改動全部復原，讓「探索另一個兄弟分支」時看到的狀態跟「還沒做過這個選擇」時完全一樣。

Failure Modes：

1. 忘記撤銷選擇（un-choose），導致狀態污染後續分支：如果path.removeLast() 被省略或寫錯位置，探索完一個分支後，path裡殘留的元素會污染下一個兄弟分支的探索，得到錯誤或重複的結果——這是 backtracking 最常見、也最難除錯的 bug，因為程式不會報錯，只是輸出結果不對。
2. 加入結果時直接存參照而不是複製：result.append(path)（存參照）而非 result.append(copy(path))（存快照）——因為path 這個 slice/陣列會在後續探索中被持續修改，等所有遞迴呼叫結束後，result 裡每個「結果」實際上都指向同一份、已經被清空的 path，得到一堆空結果或完全相同的結果。
3. 剪枝條件寫得太晚（在遞迴呼叫內部才檢查）而不是在呼叫前檢查：把 isValid 檢查放進遞迴函式的第一行（而不是呼叫前的 for迴圈內），仍然能得到正確結果，但會多付出一次不必要的函式呼叫開銷，對深度/分支因子大的問題會有可觀的效能差異。

Backend Applications：設定檔/依賴組合的驗證（例如給定一組互斥或依賴的 feature flag，窮舉所有合法組合來做測試矩陣）、排班系統窮舉合法班表（每個人的班次組合需滿足連續工時、休息時間等約束，用剪枝提早放棄違反約束的部分排班）、SQL 查詢優化器在決定 join 順序時（多表 join 的順序數量是階乘級，優化器用類似 backtracking + 剪枝的策略搜索代價最小的 join 順序，見 Day 32 Query Planner）都是 backtracking「窮舉＋剪枝」思路的實務應用。

What：Dynamic Programming（DP）是一種系統性地把「有重疊子問題的遞迴」用一張表（快取）記住每個子問題的答案，避免重複計算，把指數級的暴力遞迴壓到多項式級的技巧；DP 不是一種資料結構，也不是特定演算法，而是「辨識問題結構、用表格避免重算」的一套方法論。

Mechanism — State → Transition → Base Case → Order：這四步驟是推導任何 DP 問題的通用框架，缺一不可：

1. State（狀態）：定義「子問題」需要哪些變數才能唯一描述——通常對應遞迴函式的參數。狀態定義錯誤（少了一個維度）是 DP 最常見的失敗原因，因為少了某個維度會讓「同一個 state」實際代表多個不同的子問題，快取會存錯答案。
2. Transition（轉移方程）：描述「一個狀態的答案」怎麼由「更小的狀態」組合得到，這是遞迴關係式本身。
3. Base Case（邊界情況）：最小的、不能再往下拆的狀態，直接給出答案，是遞迴（或填表）的起點。
4. Order（計算順序）：確保計算某個狀態時，它所依賴的所有更小狀態都已經算完——bottom-up 版本要明確決定填表的迴圈方向（例如由小到大），top-down 版本則靠遞迴呼叫本身天然保證順序正確（先呼叫子問題，子問題算完才回傳）。

完整推導範例——0/1 Knapsack（0/1 背包問題）：給定 n 件物品，每件有重量 weight[i] 與價值 value[i]，背包容量上限 W，每件物品只能選 0 次或 1 次（不能拆分、不能重複拿），求能裝進背包的最大總價值。

• State：dp[i][w] = 「只考慮前 i 件物品、背包容量上限為w 時，能達到的最大總價值」。需要兩個維度：i（目前考慮到第幾件物品）與 w（目前剩餘容量）——少了 i 這個維度，dp[w]會分不清「這個 w 的最優解是否已經用過某件物品」，導致同一件物品被重複計入或狀態污染。
• Transition：對第 i 件物品，只有兩種選擇——不拿（總價值等於「前 i-1 件、容量仍是 w」的最優解）或拿（前提是weight[i] ≤ w，總價值等於「前 i-1 件、容量剩w - weight[i]」的最優解，再加上 value[i]），取兩者較大值：

``text dp[i][w] = dp[i-1][w] 若 weight[i] > w dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i]) 若 weight[i] ≤ w``

• Base Case：dp[0][w] = 0（對所有 w，沒有物品可選時總價值是 0）；dp[i][0] = 0（對所有 i，容量是 0 時裝不下任何東西）。
• Order：dp[i][*] 依賴 dp[i-1][*]，所以外層迴圈 i 必須由小到大（1 到 n），w 這個維度在同一個 i 內彼此不互相依賴，可以任意順序（但實務上也由小到大迭代）。

Top-down（memoization）vs Bottom-up（tabulation）：Top-down 直接把上面的遞迴關係式寫成遞迴函式，額外加一個快取（map[state]answer 或多維陣列），呼叫前先檢查快取是否已有答案；Bottom-up 則反過來，依 Order 步驟決定的順序，用迴圈由小到大把整張表填滿，不使用遞迴。兩者計算的狀態數與最終答案完全相同，差異在於：top-down 只計算「真正被呼叫到」的狀態（某些問題不是所有狀態都會被用到，可能更省時間），且程式碼直接對應遞迴定義、較好懂；bottom-up 沒有遞迴呼叫的 overhead 與 call stack 深度限制（Day 26 提過的 stack overflow 風險），且通常更容易進一步做空間優化（例如發現 dp[i][*] 只依賴 dp[i-1][*]，可以把二維陣列壓成一維滾動陣列，空間從 O(n·W) 降到 O(W)）。

Failure Modes：

1. 狀態定義少了一個必要維度：0/1 Knapsack 若省略 i 這個維度、只用 dp[w]，會導致同一件物品在計算過程中被「拿了不只一次」（因為少了「只考慮前 i 件」這個限制，內層迴圈更新dp[w] 時可能用到「本輪已經更新過、其實包含這件物品」的值），這正是 0/1 Knapsack 與「完全背包（每件物品可以拿無限次）」的關鍵區別——完全背包確實可以只用一維陣列且正向迭代 w，0/1 Knapsack 若要壓成一維陣列，w 必須反向（由大到小）迭代，才能保證同一件物品不會在同一輪內被重複使用。
2. Order 錯誤，使用了還沒計算的狀態：例如把上面 0/1 Knapsack 的 i 迴圈寫反（由大到小），會讓 dp[i-1][w] 這個查找存取到還沒計算過的值（陣列預設值，通常是 0），得到錯誤答案而不會報錯，這是 DP 最隱蔽的 bug 之一。
3. 問題其實不具備最優子結構，卻硬套 DP：子問題之間的最優解不一定能簡單組合成全局最優解時（例如額外附加了「相鄰選擇之間差值必須恰好等於某個變動限制」這類會破壞子問題獨立性的條件），套用標準 DP 轉移方程會得到錯誤結果——判斷一個問題是否具備最優子結構，是推導 DP 前必要的第一步，不是所有「看起來需要選擇」的問題都適合 DP（例如需要真正窮舉所有排列的問題可能要 Day 28 的 Backtracking）。

Backend Applications：diff 工具（git diff）與拼字檢查/模糊搜尋（fuzzy search，例如搜尋建議「您是不是要找 XXX」）背後常用 Edit Distance（Levenshtein Distance，計算把一個字串轉換成另一個字串所需的最少插入/刪除/替換次數）——這是標準的二維 DP，dp[i][j] 代表「字串 A 前 i 個字元轉換成字串 B 前 j 個字元所需的最少操作數」；API 限流的 token bucket 演算法計算「目前累積可用的請求配額」時，也是一種簡化版的狀態遞推（雖然通常不需要完整的表格，但轉移方程的思路相同：目前配額 = 上一刻配額 + 這段時間補充的量，取上限）；資料庫查詢優化器評估多表 join 的執行計畫代價時，某些實作用 DP 記住「join 前 k 張表的最小代價計畫」，避免對每種 join 順序重新算一次代價（這與 Day 28 Backtracking 提到的 join 順序搜索是同一個問題的兩種不同解法策略）。

陌生題（Core Fundamentals 要求）：一個文件審核系統要決定「最多可以核准哪些互不衝突的審核任務」——每個任務有 start[i]、end[i]（佔用審核員的時間區間，視為半開區間 [start, end)，end[i] == start[j] 視為首尾相接、不算衝突）與 weight[i]（這個任務的優先權重），任務之間如果時間區間重疊就不能同時核准（審核員一次只能審一個），目標是選出一組互不重疊的任務，使總權重最大。不能直接寫 code，先回答：

為什麼貪婪法（例如優先選權重最高的任務）在這裡不一定正確？該怎麼用 DP 推導？

推導：貪婪法的反例——如果權重最高的任務時間區間橫跨了另外幾個較小但總權重更高的任務，優先選權重最高的那個會排擠掉更好的組合，貪婪的「當下最優」不保證「全局最優」（這與 Day 30 會討論的、貪婪法真正適用的場景形成對比）。改用 DP：先把所有任務依 end[i]由小到大排序（排序後才能用「上一個不衝突任務」這個概念，這也是為什麼 Sorting 是 Day 25 排在 DP 之前的原因之一）。State：dp[i] = 「只考慮排序後前 i 個任務時，能達到的最大總權重」。Transition：對第 i 個任務，要嘛不選它（dp[i] = dp[i-1]），要嘛選它（找出排序後所有 end[j] ≤ start[i] 的任務中 j 最大的那個，dp[i] = dp[j] + weight[i]，這裡的 j 可以用 Binary Search 在排序後的 end 陣列上找到，呼應 Day 24），取兩者較大值。Base Case：dp[0] = 0（沒有任務時總權重是 0）。Order：i 由小到大（依排序後順序），因為 dp[i] 依賴的 dp[j]（j < i）一定已經算過。

再寫 code：實作上述解法（含排序、Binary Search 找 j、DP 遞推），對測資tasks = [(1,3,5), (2,5,6), (4,6,5), (6,8,4)]（(start,end,weight)，依 end 排序後恰好是原順序）驗證：dp[1]=5（選任務 1）、dp[2]=max(5, 0+6)=6（任務 2 與任務 1 衝突，不如只選任務 2 本身，但仍不如後面選任務 1+3）、dp[3]=max(6, dp[1]+5=10)=10（選任務 1+3）、dp[4]=max(10, dp[3]+4=14)=14（選任務 1+3+4）——最終答案14（選任務 1、3、4，總權重 5+5+4=14），且直接驗證「優先選權重最高的任務 2（權重 6）」的貪婪解只能再接上任務 4（6+4=10），確實劣於 DP 找到的 14，證實此問題不能用貪婪法。

What：Greedy（貪婪法）在每一步都做「目前看起來最好」的選擇，不回頭、不考慮這個選擇對未來造成的全部後果，直接組裝出最終答案；只有在問題具備特定數學性質（下面會展開）時，這種「短視」的做法才恰好也是全局最優解。

Mechanism — Exchange Argument（交換論證）：證明一個 Greedy 選擇規則正確的標準方法：假設存在一個「不遵守 Greedy 規則」但比 Greedy 解更好（或至少一樣好）的最優解，證明可以把這個最優解裡「不符合 Greedy 規則」的部分，逐步「交換」成符合 Greedy 規則的選擇，且每次交換後解的品質不會變差——如果能證明這件事，代表「一路都遵守 Greedy 規則」的解至少不劣於任何其他解，也就是 Greedy 解本身就是最優解之一。用活動選擇問題（Activity Selection）示範：給一組有起訖時間的活動，選出最多數量的互不重疊活動（注意這裡是最大化活動數量，跟 Day 29 陌生題的「最大化總權重」是不同的目標函式）。Greedy 規則：永遠優先選「結束時間最早」的活動。交換論證：假設最優解 O 沒有優先選結束最早的活動 A，而是選了另一個結束更晚的活動 B 作為第一個活動——因為 A 結束得比 B 早，把 O 裡的 B 換成 A，A 之後空出的時間只會更多不會更少（A 結束更早），所以 O 剩下的活動安排完全不受影響、還是合法的，活動數量不變——這代表「換成選 A」永遠不會讓解變差，因此「優先選結束最早的活動」這個 Greedy 規則是安全的。

Failure Modes：

1. 目標函式换了，貪婪規則就不再成立：Day 29 陌生題已經示範——「最大化活動數量」用「結束最早優先」是對的，但换成「最大化總權重」後，同一個「結束最早優先」的規則不再保證最優（可能為了塞更多活動而放棄了少數幾個高權重活動），必須改用 DP。同一個問題只要目標函式一變，原本驗證過的 Greedy 規則就必須重新證明，不能直接沿用。
2. 找零/背包這類問題裡，貪心對某些輸入集合失效：如果硬幣面額是 {1, 3, 4}，要湊出金額 6，貪心（每次拿能拿的最大面額）會先拿 4、剩 2、再拿兩個 1，共 3 枚硬幣；但最優解是 3+3，只需要 2 枚——這說明貪心找零只在面額系統具備「canonical」性質（例如美元硬幣 {1,5,10,25}）時才保證最優，一般情況必須用 Day 29 的 DP（Coin Change）。
3. 忽略「排序依據選錯」導致貪心規則名不符實：例如活動選擇問題若排序依據錯用「開始時間最早」而非「結束時間最早」，會導致優先選到一個佔用時間很長的活動，排擠掉後面原本能塞下的更多活動，貪心規則本身沒錯，但排序的 key 選錯就等於换了一個不成立的規則。

Backend Applications：Rate limiter 的 token bucket 演算法（每個時間點貪婪地用「目前可用的 token 數」決定是否放行請求，不回頭考慮未來的流量分佈）；負載平衡器的「最短佇列優先」（shortest-queue-first）策略——每次新請求進來，貪婪地分配給目前佇列最短的伺服器，這在多數流量分佈下接近最優，但在請求處理時間差異極大時可能失效（見 Failure Mode 的類比：目標函式其實是「總完成時間」而非「即時佇列長度」）；快取淘汰策略中的 LFU（Least Frequently Used，貪婪地淘汰目前使用頻率最低的項目）也是一種貪婪策略，同樣只在存取模式符合特定假設（近期頻率能代表未來頻率）時才接近最優。

練習（Greedy）：解 LeetCode 55 — Jump Game（給一個陣列nums，nums[i] 代表在位置 i 最多能往前跳幾步，判斷能不能從位置 0 跳到最後一個位置）。貪婪解法：維護一個變數 maxReach（目前為止，從頭開始所有可達位置中，能到達的最遠位置），從左到右掃描每個位置 i：如果 i > maxReach 代表這個位置根本到不了，直接回傳 false；否則更新 maxReach = max(maxReach, i + nums[i])。用交換論證解釋為什麼「貪婪地維護最遠可達距離」是安全的：如果存在某條路徑能到達位置 j，那麼「用最遠可達距離」這個單一數字，永遠不會漏掉任何一條實際可行的跳躍路徑（因為它是所有已知可達位置中「往前跳最遠」的那個上界，其他較近的可達位置不可能跳得比它更遠）。用 nums=[2,3,1,1,4]（答案 true）與 nums=[3,2,1,0,4]（答案 false，因為位置 3 的 maxReach 卡在 4、跳不過那個0）驗證。

What：Day 27 已經建立 DFS/BFS 這兩種走訪機制本身；本節把它們應用在具體的圖問題上——最短路徑（無權重用 BFS、有權重用 Dijkstra）、連通性（Union-Find 判斷任兩節點是否連通）、拓樸排序（在有向無環圖上，找出一個符合所有依賴順序的線性排列）。

• Dijkstra（單源最短路徑，非負權重）：本質上是把 BFS 的 queue 換成依「目前已知最短距離」排序的 priority queue（min-heap，Phase 02 Day 17）——每次從 priority queue 取出「目前距離起點最近、且還沒確定最終距離」的節點，確定它的最短距離（一旦被取出就不會再變小，這是 Dijkstra 正確性的核心：因為所有邊權重非負，之後才被處理的節點距離只會更遠，不可能反過來提供更短的路徑），再用它去更新（relax）所有鄰居的暫定距離。這是一個 Greedy 演算法——「每一步都確定目前已知最近的節點」正是 Greedy 的選擇規則，能證明正確是因為非負權重保證了「確定順序」不會被後來的邊推翻，這也解釋了為什麼 Dijkstra 不能處理負權重邊（負權重會讓「已確定」的最短距離之後被更短的路徑推翻，違反 Greedy 選擇規則的前提）。

``text func dijkstra(graph, start) {dist := {start: 0, 其他節點: infinity}pq := minHeap{(0, start)} // (距離, 節點)while !pq.empty() {(d, node) := pq.popMin()if d > dist[node] { continue } // 已有更短距離被處理過 for (neighbor, weight) in graph[node] {newDist := dist[node] + weight if newDist < dist[neighbor] {dist[neighbor] = newDist pq.push((newDist, neighbor))}}}return dist}``

• Union-Find（連通性）：維護一個「每個節點屬於哪個連通元件」的資料結構，支援兩個操作：find(x)（找出 x 所屬連通元件的代表節點）與 union(x, y)（把 x、y 所屬的兩個連通元件合併成一個）。用「每個節點記錄自己的 parent，根節點的 parent 是自己」實作，find 沿著 parent 鏈往上走到根節點；搭配 path compression（find 過程中把沿途每個節點的 parent 直接指向根節點，壓平樹的高度）與 union by rank/size（合併時把較小的樹接到較大的樹底下），均攤後每次操作接近 O(1)（嚴格來說是 O(α(n))，α 是反阿克曼函數，成長極慢，實務上視為常數）。
• 拓樸排序（Topological Sort）：只對有向無環圖（DAG）有意義，找出一個節點排列順序，使得對每條邊 u → v，u 都排在v 前面。兩種標準實作：Kahn's algorithm（BFS 版）——先計算每個節點的入度（in-degree，有幾條邊指向它），把入度為 0 的節點（沒有任何前置依賴）全部加入 queue，每次取出一個節點加入結果、並把它所有鄰居的入度減一，入度變成 0 就加入 queue，直到 queue 空；DFS 版——對每個節點做 DFS，一個節點的所有鄰居都遞迴處理完後，把這個節點加入結果的最前面（或用一個 stack，最後反轉），因為「所有鄰居都處理完」代表這個節點沒有更多依賴需要排在它前面。兩種版本都能順便偵測環：Kahn's algorithm 結束後如果處理過的節點數少於總節點數，代表剩下的節點都卡在環裡（入度永遠不會歸零）；DFS 版本則是在遞迴路徑上維護一個「目前在這條路徑上」的標記，若 DFS 過程中碰到一個「目前在路徑上」的節點，代表找到了環。

Failure Modes：

1. 對含負權重邊的圖使用 Dijkstra：如上方 Mechanism 解釋，Dijkstra 的正確性依賴「非負權重」這個前提，含負權重邊時必須改用 Bellman-Ford（能處理負權重，但時間複雜度更高，O(V×E)，本 Phase 不展開）。
2. Union-Find 沒有做 path compression / union by rank，退化成線性鏈：如果每次 union 都不考慮樹的大小、任意把一棵樹接到另一棵樹下面，且 find 不做路徑壓縮，最差情況下（一路都接成一條鏈）find 會退化成 O(n)，失去 Union-Find 應有的效率優勢。
3. 對有環的圖嘗試拓樸排序卻沒有偵測環，得到不完整或錯誤的排序：如果任務排程系統的依賴圖裡不小心出現循環依賴（A 依賴 B、B 依賴 A），拓樸排序理論上無解——沒有偵測環的實作可能只是靜默回傳一個不完整的排序（漏掉環裡的節點），比直接報錯更危險，因為呼叫端可能誤以為排序是完整、正確的。

Backend Applications：建置系統（build system，例如 Bazel、Make）用拓樸排序決定編譯順序（先編譯沒有依賴的模組，再編譯依賴它們的模組），並用環偵測擋下循環依賴的設定；分散式系統中判斷「兩個節點是否在同一個 partition/cluster」用 Union-Find（例如 Kruskal's 最小生成樹演算法，本身就是「依權重排序邊、用 Union-Find 判斷加入這條邊會不會形成環」，常用於網路拓樸設計）；路由系統計算「兩個服務之間延遲最低的路徑」用 Dijkstra（把延遲當作邊權重）；Day 27 提過的依賴解析（Go module、任務 DAG）在確認「不存在循環依賴」（DFS 環偵測）後，用拓樸排序決定實際的建置/執行順序，兩者往往是同一個依賴圖上的連續兩個步驟。

六步驟陌生題示範（對應 Day 30 收尾驗收）：LeetCode 207 —Course Schedule（給定 numCourses 門課與一組先修關係prerequisites[i] = [a, b]（代表要修 a 必須先修 b），判斷是否可能修完所有課程）。

1. Brute Force：對每一門課，遞迴檢查它的所有先修課程是否都能修完（遞迴檢查先修課程的先修課程……），沒有記錄「目前檢查路徑上有哪些課程」時，遇到循環依賴會無窮遞迴下去；即使加上簡單的重複檢查，未經整理的暴力法也可能對同一門課的先修鏈重複驗證多次。
2. Bottleneck：問題的本質是「這張『先修關係』圖是否存在環」——只要有環（例如 A 依賴 B、B 依賴 A），代表這些課程永遠無法排出合法的修課順序；暴力遞迴檢查的瓶頸在於沒有系統性地追蹤「目前遞迴路徑上」與「已經確認沒問題」的節點，導致重複驗證與無法正確偵測環。
3. Pattern：這是圖上的環偵測問題，對應 Day 27 DFS 與本節拓樸排序的環偵測技巧——把 prerequisites 轉換成有向圖（b → a代表 b 是 a 的先修課），問題等價於「這個有向圖是否為 DAG（無環）」。
4. Optimal Approach：對每個節點做 DFS，維護三種狀態：unvisited（還沒檢查）、visiting（目前在這條遞迴路徑上，還沒確認完成）、visited（已確認這個節點與它所有後續依賴都沒有環）。DFS 過程中如果碰到一個標記為 visiting 的節點，代表目前的遞迴路徑繞回了自己，找到環，直接回傳 false；一個節點的所有鄰居都確認沒有環之後，把它標記為 visited（之後不需要再檢查，避免重複驗證同一門課的先修鏈）。也可以改用 Kahn's algorithm（BFS 版拓樸排序）：計算所有課程的入度，入度為 0 的先加入 queue，逐一處理並讓後續課程入度遞減，最後檢查「成功排入結果的課程數」是否等於 numCourses，不等於就代表有環。
5. Complexity：時間 O(V+E)（V 為課程數，E 為先修關係數，DFS 或 Kahn's algorithm 都是每個節點與每條邊最多處理一次）；空間 O(V+E)（鄰接表儲存圖 + 狀態標記/入度陣列）。
6. Code：實作上述 DFS 三態版本，對測資 numCourses=2,prerequisites=[[1,0]]（答案 true，修課順序 0 → 1）與numCourses=2, prerequisites=[[1,0],[0,1]]（答案 false，0 依賴 1、1 依賴 0，形成環）驗證。