-
隨機化
鎖定
隨機化簡介
隨機化(Randomization)
隨機化算法
在我們的生活中,人們經常會去擲色子來看結果,投硬幣來決定行動,這就牽涉到一個問題:隨機。
計算機為我們提供好了隨機方法(部分計算器也提供了),那麼對於有些具有瑕疵的算法,如果配上隨機化算法的話,又是可以得到一樣不到的結果。
[1]
這種算法看上去是憑着運氣做事,其實,隨機化算法是有一定的理論基礎的,我們可以想象,在[1,10000]這個閉區間裏,隨機1000次,隨機到2這個數的幾率是多大,何況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。那麼很容易得知,隨機化算法如果隨機100次,能都到的結果基本上就正確了,而隨機時的時間消耗是O(1),只需要判斷沒有隨機重複即可,判重的時間複雜度也為O(1),並且最多隨機100次,這樣就可以有效地得到答案,最大運算次數為:O(100n),這是在計算機的承受範圍內(1000ms)的。
再舉一個例子:
而制約快速排序的有兩個:一是數據,越無序的數據,快排的速度越快;二是中間點的枚舉。
因為兩個制約條件都與隨機有着不可分開的關係。
所以,在快速排序中加入隨機化算法無疑是十分重要的。
隨機化運用
(1)數據讀入時,隨機排放數據位置。
(2)中間點的枚舉進行多次隨機化後決定。
這樣就基本上將快速排序的時間複雜度維持在最好狀態。
- 詞條統計
-
- 瀏覽次數:次
- 編輯次數:14次歷史版本
- 最近更新: 晨光与真彩7