🎯 什麼情境該想到我
分工：
append的聚合法推導 → 堆疊與佇列；雜湊表 rehash 的攤還分析與「攤還 O(1) 不代表延遲穩定」→ 雜湊表；併查集的攤還 α(n) → 併查集。這張補三種方法的完整對照與 Go 真實的擴容公式。
當一個操作「偶爾很貴、多數很便宜」（如動態陣列滿了才擴容），你想算「一連串操作」的整體平均成本時。
⚙️ 怎麼用（三種方法擇一）
攤還分析算的是「一序列操作的總成本 ÷ 操作數」，而非單次最壞。
- 聚合法（Aggregate）：直接算 n 個操作的總成本，再除以 n。
- 記帳法（Accounting）：對便宜操作「多收費」存起來，用來支付未來昂貴操作。
- 位能法（Potential）：定義一個位能函數，把成本變化攤到整個序列。
經典例：動態陣列 push——雖然擴容那次是 O(n)，但攤還到每次 push 是 O(1)。
★ 同一題用三種方法算：動態陣列的 push
設定：容量滿了就加倍，搬移每個元素成本 1，寫入一個元素成本 1。
1. 聚合法——直接加總
插入 n 個元素，擴容發生在大小為 1, 2, 4, …, 不超過 n 時，搬移總量 。加上 n 次寫入，總成本 ，平均每次 < 3 → O(1)。
2. 記帳法——每次多收錢存起來
每次 push 收 3 元：1 元付自己的寫入，2 元存在這個元素身上。容量 k 滿了要擴到 2k 時，上次擴容之後插入的 k/2 個元素身上各有 2 元、共 k 元，剛好付 k 個元素的搬移費——每個新元素付自己一份，再替前半段的一個舊元素付一份。存款永遠不會變成負的，所以每次攤還成本 3。
3. 位能法——定義一個「位能」
令 （剛擴容後 size ≈ capacity/2，Φ ≈ 0；快滿時 Φ ≈ capacity）。
- 不擴容的 push：實際成本 1，Φ 增加 2 → 攤還成本 3。
- 擴容的 push（size = cap = k → 容量 2k）：實際成本 k+1（搬 k 個，寫 1 個），Φ 從 變成 ，變化 → 攤還成本 。
三種方法得到同一個答案：3。聚合法最直觀；記帳法和位能法在操作種類很多（push、pop、還會縮小容量）時更好用，因為可以對每種操作分別算。
★ Go 的 append 其實不是單純加倍
Go 1.26.4 的 runtime/slice.go（nextslicecap）：
- 舊容量 < 256：加倍。
- 舊容量 ≥ 256：每一輪
newcap += (newcap + 3*256) >> 2，也就是約 1.25 倍再加 192，平滑地從 2 倍過渡到 1.25 倍。 - 最後還會向上取整到記憶體配置器的 size class，所以實際容量常比公式算出來的大一點。
成長率變成 1.25 倍，還是攤還 O(1) 嗎？是。 對任何固定比例 的幾何成長，搬移總量是
- ：總搬移 ≤ 2n，每次攤還 ≤ 2 次搬移。
- ：總搬移 ≤ 5n，每次攤還 ≤ 5 次搬移——常數變大，但仍是 O(1)。
取捨：成長率越小，浪費的空間越少（大 slice 不會一次多拿一倍記憶體），但搬移次數越多。Go 選擇小 slice 用 2 倍（快）、大 slice 用 1.25 倍（省記憶體）。
實務推論：知道最終大小時，make([]T, 0, n) 預先配置可以把搬移降到 0——這不改變 Big-O，但省下的常數在熱路徑上很可觀。
★ 攤還 vs 平均 vs 最壞：三個不同的保證
| 保證了什麼 | 靠什麼 | |
|---|---|---|
| 最壞情況 | 每一次操作都不超過 X | 無假設 |
| 攤還 | 任何一連串 n 次操作的總成本不超過 n·X | 無機率假設，對任何輸入序列都成立 |
| 平均（期望） | 對隨機輸入，單次成本的期望值是 X | 需要輸入分布或隨機化的假設（例：快速排序的期望 O(n log n)） |
攤還是一個「總量」保證，不是「每次」保證：延遲敏感的系統（每個請求都要 < 1ms）不能只看攤還——那一次 O(n) 的擴容就會變成一次延遲尖峰。
🧪 我實際套用的紀錄
- 2026-07-15：（待填）
⚠️ 注意
-
攤還是「序列平均」不是「機率平均」——它保證的是總量上限，不靠輸入分布假設。
-
攤還分析的前提是「從空的狀態開始」：如果你拿到一個剛好快滿的資料結構，接下來的第一次操作就可能很貴。攤還保證的是整個序列，不是從序列中間取一段。
🔗 相關工具
- 工具-時間複雜度分析、工具-儲存引擎B-Tree與LSM-Tree（LSM compaction 的攤還成本）