基本介紹
- 中文名：隨機化算法
- 特點：可以得到意想不到的結果
- 次數：隨機1000次
- 對應：比較難於掌控
隨機化算法概述,定義,舉例,例一,例二,
隨機化算法概述
在我們的生活中，人們經常會去擲色子來看結果，投硬幣來決定行動，這就牽涉到一個問題：隨機。
計算機為我們提供好了隨機方法（部分計算器也提供了），那么對於有些具有瑕疵的算法，如果配上隨機化算法的話，又是可以得到意想不到的結果。
定義
這種算法看上去是憑著運氣做事，其實，隨機化算法是有一定的理論基礎的，我們可以想像，在[1,10000]這個閉區間裡，隨機1000次，隨機到2這個數的幾率是多大(約為0.1)，何況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。那么很容易得知，隨機化算法如果隨機300次，能得到的結果基本上就正確了(機率為1-(209/210)^300，約為0.76)，而隨機時的時間消耗是O(1)，只需要判斷沒有隨機重複即可，判重的時間複雜度也為O(1)，並且最多隨機300次，這樣就可以有效地得到答案，最大運算次數為：O(300n)，這是在計算機的承受範圍內（1000ms）的。
從這裡就能看出，隨機化算法是一個很好的機率算法，但是它並不能保證正確，而且它單獨使用的情況很少，大部分是與其他的算法：例如貪心、搜尋等配合起來運用。
例二
排序問題。快速排序是排序方法中較為便捷的方法之一，但是由於它極不穩定，最好的時候時間複雜度為O(n㏒n)，這裡的㏒是指以2為底的對數運算。最壞的時候能達到與普通排序方法一樣的O(n^2)。
而制約快速排序的有兩個：一是數據，越無序的數據，快排的速度越快；二是中間點的枚舉。
因為兩個制約條件都與隨機有著不可分開的關係。
所以，在快速排序中加入隨機化算法無疑是十分重要的。
運用在：
（1）數據讀入時，隨機排放數據位置。
（2）中間點的枚舉進行多次隨機化後決定。
這樣就基本上將快速排序的時間複雜度維持在最好狀態。
