[TOC] # 概述 Randomization is a fundamental technique in algorithm design,that allows programs to run quickly when the average-case behavior of an algorithm is better than the worst-case behavior. It is also heavily used in games,both in entertainment and gambling. 當算法的平均時間比最壞情況下所用的時間少時，我們可以用隨機化算法進行改進。 隨機化算法是這樣一種算法，在算法中使用了隨機函數，且隨機函數的返回值直接或者間接的影響了算法的執行流程或執行結果。隨機化算法基于隨機方法，依賴于概率大小。 # 隨機化算法分類 一般情況下，可以將隨機化算法分為四類： * 數值隨機化算法 * 蒙特卡羅算法 * 拉斯維加斯算法 * 舍伍德算法 #### 數值隨機化算法 這種算法常用于數值問題的求解。這類算法得到的往往是近似解。 #### 蒙特卡羅算法 用于求問題的準確解。對于許多問題，近似解毫無意義。 #### 拉斯維加斯算法 不會得到不正確的解。 #### 舍伍德算法 該算法總能求得問題的一個解，且所求得的解總是正確的。當一個確定性算法在最壞情況下的計算復雜性與其平均情況下的計算復雜性有較大差別時，可在這個算法中引入隨機性將它改造成為一個舍伍德算法，消除或者減少問題的好壞實例間的這種差別。舍伍德算法的精髓不是避免算法的最壞情形行為，而是設法消除這種最壞情形行為與特定實例之間的關聯性。