隨機化演算法（）是在邏輯或執行過程中使用隨機性的演算法。這類演算法通常使用均勻隨機位元作為輔助輸入，以引導演算法的行為，並期望在所有可能的隨機選擇之平均情況下取得良好效能。因此，隨機化演算法的執行時間、輸出結果，或兩者都可能是隨機變數。
隨機化演算法可依其對正確性與執行時間的保證分為不同類型。一類演算法會使用隨機輸入，並總是以正確答案終止，其執行時間可能根據隨機選擇而改變，這類演算法稱為拉斯維加斯演算法。另一類演算法通常具有固定或有界的執行時間，但可能有一定機率產生錯誤結果或無法得到結果，這類演算法稱為蒙地卡羅演算法。 同年，霍爾也發表了快速選擇演算法；該演算法可在期望線性時間內找出列表中的中位數元素。 至於是否存在確定性的線性時間選擇演算法，直到 1973 年才獲得解答。
資料結構
最早的隨機化資料結構之一是雜湊表。雜湊表由 IBM 的漢斯·彼得·盧恩於 1953 年提出。 盧恩的雜湊表使用鏈結法處理衝突，是鏈結串列的早期應用之一。
例子
快速排序
快速排序是常見且廣泛使用的演算法，也是隨機性發揮作用的典型例子。許多確定性版本的快速排序，對於某些類型的退化輸入，例如已排序的陣列，可能需要 O(n^2) 時間才能完成對 n 個數的排序；實際會導致此情況的輸入類型，取決於演算法選擇基準值的方式。
然而，若演算法每次都均勻隨機選取基準值，則無論輸入資料本身具有何種特性，快速排序被證明有很高的機率在 O(n \log n) 時間內完成。
參考資料
评论 (0)