隨機化

隨機化演演算法

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

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

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

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

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

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

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

分析：

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

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

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

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

再舉一個例子：

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

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

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

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

運用在：

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

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

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