順序統計量與中位數

🎯 什麼情境該想到我

當你「只要第 $k$ 個，不需要全部排好」的時候——中位數、p95／p99 延遲、Top-K 熱門、離群值門檻。
★ 完整排序是 $O(n\log n)$，但選擇只需要 $O(n)$。 而且實務上有三種做法，選錯差很多。

⚙️ 怎麼用（三種做法與選擇判準）

★ 三種做法的對照（這張表是本頁的核心）

做法	時間	空間	何時用
① 先排序再取	$O(n\log n)$	$O(1)$ 或 $O(n)$	$k$ 接近 $n$；或本來就要排序；或 $n$ 很小（別過度優化）
② 大小為 $k$ 的堆	$O(n\log k)$	$O(k)$	★ $k\ll n$，或資料是串流／裝不進記憶體
③ Quickselect	平均 $O(n)$，最差 $O(n^2)$	$O(1)$	★ 資料全在記憶體、只要一次、$k$ 任意

★ 實務上的判準：

• 資料是串流／太大裝不下 → ② 堆（這是唯一可行的）
• 要算 p99 這種 $k$ 很大的 → ② 的堆會變成 $O(n\log n)$，改用 ③ 或 ①
• 全在記憶體、一次性 → ③ Quickselect
• 會重複查詢不同的 $k$ → ① 排序一次，之後每次 $O(1)$

② 堆的做法（Top-K 最常用）

要「最大的 $k$ 個」→ 維護一個大小為 $k$ 的「最小堆」（反直覺但正確）：

import "container/heap"
 
// 最大的 k 個：用最小堆，堆頂是「目前 top-k 裡最小的」
func TopK(stream []int, k int) []int {
    h := &IntHeap{}                    // 最小堆
    heap.Init(h)
    for _, v := range stream {
        if h.Len() < k {
            heap.Push(h, v)
        } else if v > (*h)[0] {        // ★ 比目前最小的還大，才值得換進來
            heap.Pop(h)
            heap.Push(h, v)
        }
    }
    return *h
}

★ 為什麼是最小堆：堆頂是這 $k$ 個裡最小的，也就是「門檻」。
新元素只要不超過門檻就直接丟掉——$O(1)$ 判斷。超過才付 $O(\log k)$ 把門檻換掉。

★ 它的關鍵優勢：只需要 $O(k)$ 記憶體，而且是串流演算法（資料只掃一遍、不用全部留著）。
Go 的 container/heap 官方定義就是最小堆（“each node is the minimum-valued node in its subtree”，見 二元堆積）。

③ Quickselect（平均線性）

就是 快速排序，但分割後只遞迴「包含答案的那一邊」。

// 回傳第 k 小的元素（k 從 0 開始），會原地打亂 a
func QuickSelect[T cmp.Ordered](a []T, k int) T {
    for {
        if len(a) == 1 {
            return a[0]
        }
        p := partition(a)          // 見 [[快速排序]]
        switch {
        case k == p:
            return a[p]
        case k < p:
            a = a[:p]              // ★ 只遞迴左邊
        default:
            a = a[p+1:]            // ★ 只遞迴右邊，k 要跟著平移
            k -= p + 1
        }
    }
}

★ 為什麼平均是 $O(n)$ 而不是 $O(n\log n)$：

快排每層要處理所有元素（兩邊都遞迴），所以是 $n+n+n+\dots$（$\log n$ 層）。
Quickselect 每層只處理一半：

$n+\frac{n}{2}+\frac{n}{4}+\frac{n}{8}+\cdots =2n=O(n)$

等比級數收斂成常數倍 —— 這就是「只遞迴一邊」帶來的量級差異。
同樣的道理也解釋了 二分搜尋 為什麼是 $O(\log n)$ 而不是 $O(n)$。

最差仍是 $O(n^2)$（每次都切出極端不平衡），所以要隨機化 pivot。

Median of Medians（最差 $O(n)$）

CLRS 的經典結果：存在最差情況也是 $O(n)$ 的選擇演算法。
做法是把元素每 5 個一組取中位數，再遞迴求「這些中位數的中位數」當 pivot，
可證明這個 pivot 至少能排除 30% 的元素。

⚠️ 理論上漂亮，實務上幾乎沒人用——常數太大，隨機化的 quickselect 在真實資料上快得多。
它的價值是「證明線性選擇是可能的」，不是拿來寫。

★ 實務：p95 / p99 延遲怎麼算

直接排序全部樣本是最簡單也最準的——如果樣本放得下。

大規模時的實務做法：

方法	說明
固定寬度直方圖／bucket	預先定好 bucket 邊界（如 1ms, 2ms, 5ms, 10ms…），只累加計數。記憶體固定、可合併，代價是解析度受 bucket 粒度限制 —— Prometheus histogram 就是這樣
t-digest / HDR Histogram	專門為分位數設計，尾端解析度高（p99、p999 準），可合併
★ 可合併性是關鍵	多台機器的分位數不能直接平均！「三台機器的 p99 各是 100ms」不代表整體 p99 是 100ms。 必須用可合併的結構（直方圖、t-digest）在原始資料層合併後再算

★ 「p99 不能平均」是實務上極常見的錯誤，值得單獨記住。

🧪 我實際套用的紀錄

• （待填）

⚠️ 注意 / 什麼時候不適用

• ★ Quickselect 會修改輸入陣列（原地分割）。不能動原始資料就要先複製，那就多了 $O(n)$ 空間。
• Quickselect 必須隨機化 pivot，否則已排序輸入會退化成 $O(n^2)$（同 快速排序）。
• ★ 資料是串流時只能用堆。Quickselect 需要全部資料在手上。
• $k$ 很大時堆的做法會退化。$k=n/2$（中位數）時 $O(n\log k)\approx O(n\log n)$，還不如直接排序。
• 重複值很多時，quickselect 要用三路分割，否則會退化。
• 多台機器的分位數不可平均（見上）。
• $n$ 很小就直接排序。$n<1000$ 時所有方法都是微秒級，選最好懂的那個。

🔗 相關工具

• 快速排序 —— Quickselect 是它「只遞迴一邊」的變體
• 二元堆積 —— Top-K 的資料結構，以及為什麼用最小堆找最大值
• 堆積排序 —— 完整排序的對照組
• 二分搜尋 —— 同樣是「只遞迴一邊」帶來的複雜度下降
• 工具-遙測與監控 —— p95/p99 在實務上的量測
• 演算法導論