🎲 隨機化演算法
隨機化不是不確定，而是利用隨機性來簡化問題。
- Monte Carlo 演算法：有可能出錯，但錯誤率可控制
- Las Vegas 演算法：永遠正確，但執行時間是隨機的
隨機化演算法在密碼學、大數據、機器學習中無所不在。
🔥 Vibe Coding 核心 Prompt
【隨機化快速選擇詠唱範例】
「請幫我實作 Randomized Quickselect：1. 實作一個函式找到陣列中第 K 小的元素。2. 隨機選擇 pivot 而不是固定選第一個。3. 分析為什麼隨機化可以避免最壞情況 O(n²)。4. 比較固定 pivot 與隨機 pivot 在不同輸入下的效能。5. 用實驗證明期望時間複雜度為 O(n)。」
🎯 課程大綱
- Monte Carlo vs Las Vegas
- Randomized Quickselect / Quicksort
- 隨機化最小割
- 密碼學中的隨機化
- 機率分析與集中不等式
課程導覽：這堂課你會學到什麼？
隨機化演算法（Randomized Algorithm）是演算法設計中強大的策略——
第一章：Monte Carlo vs Las Vegas
兩種隨機化演算法的分類。Monte Carlo 時間固定但可能錯；Las Vegas 保證正確但時間隨機。這決定了你該在哪種場景使用哪種策略。
第二章：隨機化快速排序
經典的 Las Vegas 案例。為什麼隨機選 pivot 可以避免 Worst Case O(n²)？理解這個問題的答案等於理解了隨機化演算法的價值。
第三章：Monte Carlo 方法
從圓周率估計到光線追蹤——Monte Carlo 的核心思想是「用隨機抽樣估計複雜問題的答案」。
第四章：最小割與 Contraction
Karger 的隨機化 Contraction 演算法展示了一個反直覺的事實：簡單的隨機合併策略，多次執行後可以高機率找到最佳解。
第五章：水庫抽樣
當你面對無限串流資料，無法全部儲存時——水庫抽樣讓你能在 O(n) 時間內取得均勻隨機樣本，而且只需要 O(k) 的記憶體。