隨機演算法 (Randomized Algorithm)

利用隨機性解決問題的演算法

概述

隨機演算法在執行過程中引入隨機性,通常可以簡化問題或獲得更好的平均效能。隨機演算法可分為 Las Vegas 演算法(結果一定正確,執行時間隨機)和 Monte Carlo 演算法(執行時間固定,結果以高機率正確)。

蒙地卡羅法

蒙地卡羅法通過大量隨機採樣來估計數值結果。典型應用包括:

隨機化演算法範例

隨機化快速排序:隨機選擇 pivot,避免最壞情況 O(n²)。

隨機化最小割:Karger 隨機收縮演算法。

跳躍 Hash:一致性雜湊的隨機化方法。

本課程範例

相關連結