確定性演算法可以被對手構造出最壞輸入；隨機化讓對手無從預測你的行為。
Las Vegas vs Monte Carlo
隨機化演算法分兩類：
Las Vegas：結果一定正確，執行時間是隨機變數（但有好的期望值）。Randomized QuickSort 是典型——隨機選 pivot，最壞仍是 O(n²)，但期望 O(n log n)，且對手無法構造讓你每次都選到最差 pivot 的輸入。
Monte Carlo：執行時間固定，結果以高機率正確。Miller-Rabin 質數測試是典型——k 次測試後誤判機率 ≤ 4^(-k)，k=40 時誤判機率約 10^(-24)，工程上視為 0。
Reservoir Sampling：不知道總量也能均勻抽樣
資料流源源不斷，不知道總共有 n 個元素，要從中均勻隨機選 k 個。
傳統做法需要先知道 n，才能計算每個元素被選中的機率。Reservoir Sampling 不需要：
int[] reservoirSampling(int[] stream, int k) {
int[] reservoir = Arrays.copyOf(stream, k); // 前 k 個直接放入
for (int i = k; i < stream.length; i++) {
int j = random.nextInt(i + 1); // [0, i] 的均勻隨機整數
if (j < k)
reservoir[j] = stream[i]; // 以 k/(i+1) 的機率替換
}
return reservoir;
}數學歸納法可以證明：每個元素最終被選中的機率恰好是 k/n。YouTube 的「每日精選」、A/B 測試的用戶採樣，都是這個演算法的應用。
Fisher-Yates Shuffle：真正的均勻洗牌
Math.random() 直接排序不是均勻隨機的——每種排列出現的機率不相等。Fisher-Yates 保證均勻：
void shuffle(int[] arr) {
for (int i = arr.length - 1; i > 0; i--) {
int j = random.nextInt(i + 1); // [0, i]
swap(arr, i, j);
}
}從後往前，每個位置從「還沒固定的元素」裡均勻隨機選一個放入。n! 種排列，每種概率恰好 1/n!。
常見錯誤：random.nextInt(arr.length) 而不是 random.nextInt(i + 1)——這會讓某些排列出現機率更高。
Randomized Quick Select：找第 k 小，期望 O(n)
要在一堆未排序的數字裡找「第 k 小」，最直覺是排序後取——但排序是 O(n log n)，其實用不著把整組排好。Quick Select 借 QuickSort 的 partition：隨機挑 pivot 切一刀，pivot 落定後就知道它排第幾，接著只往「答案所在的那半」遞迴，另一半直接扔掉。
int quickSelect(int[] arr, int lo, int hi, int k) {
if (lo == hi) return arr[lo];
int p = partition(arr, lo, hi, lo + random.nextInt(hi - lo + 1)); // 隨機 pivot
if (p == k) return arr[p];
return p > k ? quickSelect(arr, lo, p - 1, k) // 答案在左半
: quickSelect(arr, p + 1, hi, k); // 答案在右半
}跟 QuickSort 少遞迴一半，期望複雜度從 O(n log n) 掉到 O(n)（每次只處理一邊，n + n/2 + n/4 + … = 2n）。最壞仍是 O(n²)——但那要 pivot 每次都選到極端值，隨機化之後對手沒辦法逼你走到那一步，這正是 Las Vegas 的價值：答案永遠對，慢只慢在運氣。
Miller-Rabin 質數測試
判斷一個大數 n 是否為質數。試除法需要 O(√n)，對於 64-bit 整數約 3×10⁹ 次，太慢。
Miller-Rabin 用費馬小定理的強化版：
若 p 是質數，則對任意 a，2^k 次測試後：
a^(n-1) ≡ 1 (mod n)
且這個 1 是「從 -1 轉過來的」
隨機選 k 個底數 a 測試
每個 a 如果沒被排除 → 可能是質數
被任意一個 a 排除 → 確定是合數
k 次測試後合數通過的機率 ≤ 4^(-k)
k=40：誤判概率 ≈ 10^(-24)Python 的 sympy.isprime()、Java 的 BigInteger.isProbablePrime() 底層都是 Miller-Rabin 或類似的概率質數測試。
Monte Carlo 估 π：用亂數量面積
隨機化還能拿來「量」東西。在單位正方形裡亂撒點，落在四分之一圓內（x² + y² ≤ 1）的比例，長期會逼近圓面積佔正方形的比 π/4——撒得越多越準。
double estimatePi(int n) {
int inside = 0;
for (int i = 0; i < n; i++) {
double x = random.nextDouble(), y = random.nextDouble();
if (x * x + y * y <= 1) inside++;
}
return 4.0 * inside / n;
}這是 Monte Carlo 的教科書入門例，但也暴露它的軟肋：誤差收斂速度是 O(1/√n)，想多一位精度得多撒 100 倍的點。真要算 π 有的是更快的級數解——Monte Carlo 的舞台是那些「維度高到沒有解析解」的積分，撒點反而是唯一划算的路。
五個放一起看
| 演算法 | 類型 | 主要用途 |
|---|---|---|
| Reservoir Sampling | Las Vegas | 串流 / 大資料均勻抽樣 |
| Fisher-Yates | Las Vegas | 公平洗牌 |
| Randomized Quick Select | Las Vegas | 找第 k 小 |
| Miller-Rabin | Monte Carlo | 大數質數測試 |
| Monte Carlo 積分 | Monte Carlo | 高維面積 / 積分估計 |
分界線很乾脆：要答案永遠對、只賭時間，選 Las Vegas；能接受極小誤差換固定時間，選 Monte Carlo。
🎬 互動視覺化：隨機化演算法動手玩 — 看蓄水池抽樣怎麼在資料流裡替換、Monte Carlo 撒點怎麼一點點逼近 π，隨機的收斂用眼睛看最有感。
隨機化的精髓不是「靠運氣」，而是「讓你的行為對對手不可預測」——這是確定性演算法做不到的。
接下來往哪走
- 歐拉路徑：每條邊走且只走一次 — 下一篇：回到圖論，一筆畫問題的完整解法
- Skip List 跳躍表 — 靠丟硬幣達成平衡的資料結構，隨機化思想的代表作
- Sorting 排序演算法 — Quick Sort 的 pivot 選擇就是隨機化要解的最壞情況來源