隨機化

隨機化算法是這樣一種算法，在算法中使用了隨機函式，且隨機函式的返回值直接或者間接的影響了算法的執行流程或執行結果。隨機化算法基於隨機方法，依賴於機率大小。

基本介紹

• 中文名：隨機化
• 外文名：randomization
• 說明：一種機率算法
• 介紹：算法中使用了隨機函式

簡介

隨機化（Randomization）

在一組測定值中，每個測定值都是依一定的機率獨立出現的，則稱這一組測定值的出現是隨機化的。可用遊程檢驗來確定一組測定值的出現是否是隨機化的。

算法

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

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

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

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

一個長度在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。那么很容易得知，隨機化算法如果隨機100次，能都到的結果基本上就正確了，而隨機時的時間消耗是O(1)，只需要判斷沒有隨機重複即可，判重的時間複雜度也為O(1)，並且最多隨機100次，這樣就可以有效地得到答案，最大運算次數為：O(100n)，這是在計算機的承受範圍內（1000ms）的。

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

再舉一個例子：

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

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

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

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

運用

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

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

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