機率算法

蒙特卡羅算法用於求問題的準確解。 用蒙特卡羅算法能求得問題的一個解，但這個解未必是正確的。 舍伍德算法總能求得問題的一個解，且所求得的解總是正確的。

很多算法的每一個計算步驟都是固定的，而機率算法允許算法在執行的過程中隨機選擇下一個計算步驟。許多情況下，當算法在執行過程中面臨一個選擇時，隨機性選擇常比最優選擇省時。因此機率算法可在很大程度上降低算法的複雜度。
機率算法的一個基本特徵是對所求解問題的同一實例用同一機率算法求解兩次可能得到完全不同的效果。這兩次求解問題所需的時間甚至所得到的結果可能會有相當大的差別。一般情況下，可將機率算法大致分為四類:數值機率算法，蒙特卡羅（Monte Carlo）算法，拉斯維加斯（Las Vegas）算法和舍伍德（Sherwood）算法。
數值機率算法常用於數值問題的求解。這類算法所得到的往往是近似解。而且近似解的精度隨計算時間的增加不斷提高。在許多情況下，要計算出問題的精確解是不可能或沒有必要的，因此用數值機率算法可得到相當滿意的解。
蒙特卡羅算法用於求問題的準確解。對於許多問題來說，近似解毫無意義。例如，一個判定問題其解為“是”或“否”，二者必居其一，不存在任何近似解答。又如，我們要求一個整數的因子時所給出的解答必須是準確的，一個整數的近似因子沒有任何意義。用蒙特卡羅算法能求得問題的一個解，但這個解未必是正確的。求得正確解的機率依賴於算法所用的時間。算法所用的時間越多，得到正確解的機率就越高。蒙特卡羅算法的主要缺點就在於此。一般情況下，無法有效判斷得到的解是否肯定正確。
拉斯維加斯算法不會得到不正確的解，一旦用拉斯維加斯算法找到一個解，那么這個解肯定是正確的。但是有時候用拉斯維加斯算法可能找不到解。與蒙特卡羅算法類似。拉斯維加斯算法得到正確解的機率隨著它用的計算時間的增加而提高。對於所求解問題的任一實例，用同一拉斯維加斯算法反覆對該實例求解足夠多次，可使求解失效的機率任意小。
舍伍德算法總能求得問題的一個解，且所求得的解總是正確的。當一個確定性算法在最壞情況下的計算複雜性與其在平均情況下的計算複雜性有較大差別時，可以在這個確定算法中引入隨機性將它改造成一個舍伍德算法，消除或減少問題的好壞實例間的這種差別。舍伍德算法精髓不是避免算法的最壞情況行為，而是設法消除這種最壞行為與特定實例之間的關聯性。