隨機化

簡介
　　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）中間點的枚舉進行多次隨機化後決定。
　　這樣就基本上將快速排序的時間復雜度維持在最好狀態。