本篇將主要講解隨機化算法，在正式進入主題之前，我們先談?wù)勈裁词请S機化？隨機化是一種可能影響試驗結(jié)果的無關(guān)或可能在試驗過程中變化，從而影響到最終結(jié)果。

隨機化算法，是在算法中使用了隨機函數(shù)，且隨機函數(shù)的返回值直接或間接的影響了算法的執(zhí)行流程或結(jié)果。隨機化算法基于隨機方法，依賴于概率大小。

一、隨機化算法分類

通俗的說，就是在算法執(zhí)行的某個步驟中將生成隨機數(shù)，而該隨機數(shù)將會影響到整個算法的最終結(jié)果。因此，我們可以將隨機算法大致分為以下兩類：

（1）蒙特卡洛算法(Monte Carlo)并不是一種具體的算法，而是一類算法的統(tǒng)稱。其基本思想是基于隨機事件出現(xiàn)的概率。蒙特卡洛算法得到的最終結(jié)果并不一定是正確的，我們可以通過計算算法出錯的概率值，然后進行多次求解，使得最終得到正確結(jié)果的可能性變得很高。接下來我們來討論一種蒙特卡洛算法：

（2）拉斯維加斯算法 (Las Vegas) 是另一種隨機算法，因此它具備隨機算法最為重要的特征之一 —— 基于隨機數(shù)進行求解。和蒙特卡洛算法一樣，都是一類隨機算法,所以就分別用了兩個賭城的名字命名,其實和拉斯維加斯沒關(guān)系，與 蒙特卡洛算法 (Monte Carlo) 一樣，拉斯維加斯算法也不是一種具體的算法，而是一種思想。但不同的是，拉斯維加斯算法在生成隨機值的環(huán)節(jié)中，會不斷的進行嘗試，直到生成的隨機值令自己滿意。在這過程中也許會一直無法產(chǎn)生這樣的隨機值，因此拉斯維加斯算法的時間效率通常比蒙特卡洛算法來的低，并且最終可能無法得到問題的解，但是一旦算法找到一個解，那么這個解一定是問題的正確解。

二、隨機數(shù)與偽隨機數(shù)

說一個單獨的數(shù)是「隨機數(shù)」是無意義的，所以以下我們都默認討論「隨機數(shù)列」，即使提到「隨機數(shù)」，指的也是「隨機數(shù)列中的一個元素」。

現(xiàn)有的計算機的運算過程都是確定性的，因此，僅憑借算法來生成真正 不可預測、不可重復 的隨機數(shù)列是不可能的。

然而在絕大部分情況下，我們都不需要如此強的隨機性，而只需要所生成的數(shù)列在統(tǒng)計學上具有隨機數(shù)列的種種特征（比如均勻分布、互相獨立等等）。這樣的數(shù)列即稱為 偽隨機數(shù) 序列。

隨機數(shù)與偽隨機數(shù)在實際生活和算法中的應(yīng)用舉例：

抽樣調(diào)查時往往只需使用偽隨機數(shù)。這是因為我們本就只關(guān)心統(tǒng)計特征。

網(wǎng)絡(luò)安全中往往要用到（比剛剛提到的偽隨機數(shù)）更強的隨機數(shù)。這是因為攻擊者可能會利用可預測性做文章。

OI/ICPC 中用到的隨機算法，基本都只需要偽隨機數(shù)。這是因為，這些算法往往是 通過引入隨機數(shù) 來把概率引入復雜度分析，從而降低復雜度。這本質(zhì)上依然只利用了隨機數(shù)的統(tǒng)計特征。

某些隨機算法（例如 Moser 算法）用到了隨機數(shù)的熵相關(guān)的性質(zhì)，因此必須使用真正的隨機數(shù)。

隨機化算法在考試中出現(xiàn)的次數(shù)不是很多，但是出現(xiàn)了，使用好會節(jié)省很多時間和經(jīng)歷，所以大家一定要記住隨機化是一種可能影響試驗結(jié)果的無關(guān)或可能在試驗過程中變化，從而影響到最終結(jié)果，慎重選擇。