隨機化算法

在我們的生活中，人們經常會去擲色子來看結果，投硬幣來決定行動，這就牽涉到一個問題：隨機。

計算機為我們提供好了隨機方法（部分計算器也提供了），那麼對於有些具有瑕疵的算法，如果配上隨機化算法的話，又是可以得到意想不到的結果。 ^[1] 

這種算法看上去是憑着運氣做事，其實，隨機化算法是有一定的理論基礎的，我們可以想象，在[1,10000]這個閉區間裏，隨機1000次，隨機到2這個數的幾率是多大(約為0.1)，何況1000次的隨機在計算機程序中僅僅是一眨眼的功夫。可以看出，隨機化算法有着廣闊的前景。只是由於隨機化算法比較難於掌控，所以並不是很多人都接觸過他，但肯定有很多人都聽説過。 ^[2] 

下面，我們就隨機化問題，舉一個例子：

一個長度在4..10的字符串中，需要判定是否可以在字符串中刪去若干字符，使得改變後字符串符合以下條件之一：

（1）AAAA；（2）AABB；（3）ABAB；（4）ABBA。

例如：長度為6字符串“POPKDK”，若刪除其中的“O”，“D”兩個字母，則原串變為：“PPKK”，符合條件（2）AABB。

分析：

這道題很容易想到一種算法：運用排列組合：枚舉每4個字母，然後逐一判斷。算法是可行的，但是如果需要題目中加上一句話：需要判斷n個字符串，且n<=100000，那麼這樣的耗時是不能讓人忍受①的，因為在枚舉的過程中，是非常浪費時間的。

（①：這裏是指信息學中要求算法的普遍運算時間為：1000ms）

所以這道題有可能可以藉助於隨機化算法，下面我們來算一下在10個字符中取4個字符一共有多少種取法：C(4,10)=210。那麼很容易得知，隨機化算法如果隨機300次，能得到的結果基本上就正確了(概率為1-(209/210)^300，約為0.76)，而隨機時的時間消耗是O(1)，只需要判斷沒有隨機重複即可，判重的時間複雜度也為O(1)，並且最多隨機300次，這樣就可以有效地得到答案，最大運算次數為：O(300n)，這是在計算機的承受範圍內（1000ms）的。

從這裏就能看出，隨機化算法是一個很好的概率算法，但是它並不能保證正確，而且它單獨使用的情況很少，大部分是與其他的算法：例如貪心、搜索等配合起來運用。

排序問題。快速排序是排序方法中較為便捷的方法之一，但是由於它極不穩定，最好的時候時間複雜度為O(n㏒n)，這裏的㏒是指以2為底的對數運算。最壞的時候能達到與普通排序方法一樣的O(n^2)。

而制約快速排序的有兩個：一是數據，越無序的數據，快排的速度越快；二是中間點的枚舉。

因為兩個制約條件都與隨機有着不可分開的關係。

所以，在快速排序中加入隨機化算法無疑是十分重要的。

運用在：

（1）數據讀入時，隨機排放數據位置。

（2）中間點的枚舉進行多次隨機化後決定。

這樣就基本上將快速排序的時間複雜度維持在最好狀態。 ^[1]