隨機化演算法（randomized algorithm）是在邏輯或執行過程中使用隨機性的演算法。這類演算法通常使用均勻隨機位元作為輔助輸入，以引導演算法的行為，並期望在所有可能的隨機選擇之平均情況下取得良好效能。因此，隨機化演算法的執行時間、輸出結果，或兩者都可能是隨機變數。[1]
隨機化演算法可依其對正確性與執行時間的保證分為不同類型。一類演算法會使用隨機輸入，並總是以正確答案終止，其執行時間可能根據隨機選擇而改變，這類演算法稱為拉斯維加斯演算法。另一類演算法通常具有固定或有界的執行時間，但可能有一定機率產生錯誤結果或無法得到結果，這類演算法稱為蒙地卡羅演算法。[1]
在實際應用中，隨機化演算法通常會以偽隨機數生成器取代理論上的真正隨機位元來源。不過，這樣的實作可能會偏離理論上預期的行為與數學保證，因為某些保證可能依賴理想的真正隨機數生成器。[1]
早期歷史
编辑排序
编辑快速排序由東尼·霍爾於 1959 年發現，並於 1961 年正式發表。[2] 同年，霍爾也發表了快速選擇演算法；該演算法可在期望線性時間內找出列表中的中位數元素。[3] 至於是否存在確定性的線性時間選擇演算法，直到 1973 年才獲得解答。[4]
資料結構
编辑最早的隨機化資料結構之一是雜湊表。雜湊表由 IBM 的漢斯·彼得·盧恩於 1953 年提出。[5] 盧恩的雜湊表使用鏈結法處理衝突，是鏈結串列的早期應用之一。[5]
例子
编辑快速排序
编辑快速排序是常見且廣泛使用的演算法，也是隨機性發揮作用的典型例子。許多確定性版本的快速排序，對於某些類型的退化輸入，例如已排序的陣列，可能需要 時間才能完成對 個數的排序；實際會導致此情況的輸入類型，取決於演算法選擇基準值的方式。
然而，若演算法每次都均勻隨機選取基準值，則無論輸入資料本身具有何種特性，快速排序被證明有很高的機率在 時間內完成。[1]
參考資料
编辑- ^ 1.0 1.1 1.2 1.3 Motwani, Rajeev; Raghavan, Prabhakar. Randomized Algorithms. Cambridge University Press. 1995. ISBN 978-0-521-47465-8.
- ^ Hoare, C. A. R. Algorithm 64: Quicksort. Communications of the ACM. 1961-07, 4 (7): 321. ISSN 0001-0782. doi:10.1145/366622.366644.
- ^ Hoare, C. A. R. Algorithm 65: Find. Communications of the ACM. 1961-07, 4 (7): 321–322. ISSN 0001-0782. doi:10.1145/366622.366647.
- ^ Blum, Manuel; Floyd, Robert W.; Pratt, Vaughan; Rivest, Ronald L.; Tarjan, Robert E. Time bounds for selection. Journal of Computer and System Sciences. 1973-08, 7 (4): 448–461. doi:10.1016/S0022-0000(73)80033-9.
- ^ 5.0 5.1 Knuth, Donald E. The Art of Computer Programming, Volume 3: Sorting and Searching 2nd. Addison-Wesley. 1998: 536–549. ISBN 978-0-201-89685-5.
