iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 20
0
自我挑戰組

當傳統演算法遇到新的計算模型系列 第 20

Day 20: 隨機計算模型 Randomized Algorithms -- 快速排序法

為了最後十天的內容,我們今天先來聊一下隨機演算法。絕對不是拖台前,絕對不是,絕對(被拖走)。

假想一下,我們有真正的隨機位元產生器。每詢問一次這個產生器,拿到 0 和拿到 1 的機率保證都是 0.5。有了這個公正的位元產生器,我們就可以進行丟隨機銅板的實驗了。假設我們丟 N 枚公正的銅板,令 X1, … XN 表示每一次丟銅板的結果:1 表示人頭朝上、0 表示背面朝上。令 X = X1+X2+...+XN,通常在機率的世界裡面我們會令 µ = E[X] 表示 X 的期望值,在這個例子中會是個精準的 N/2。

期望值與實驗

實際丟銅板的結果自然不會每次都 N/2: µ = N/2 只是說如果你進行無窮多次實驗,那麼逐次平均起來的結果會趨近於 N/2。想像一下:如果你交錯地不斷反覆實驗(每次實驗丟 N 個銅板)出現 0, N, 0, N, …, 這樣平均起來也是 N/2,但顯然不會符合你的直覺,畢竟這些銅板是機率上獨立被丟出的。

Chernoff Bounds

那我們該如何刻劃「其實 N 很大的話,實驗結果真的會很接近 N/2 唷」呢?事實上這件事情會牽涉到另一個機率上的觀念:集中性 (Concentration)。而事實上,我們對於丟銅板問題而言,只能說「其實 N 很大的話,實驗結果會有極高的機率 X 的值會落在 (0.5-ε)N 和 (0.5+ε)N 之間唷」而這個極高的機率,大概會是與 N 呈現指數遞減的(也就是說:如果你希望達到 1-δ 的正確率的話,你只需要進行 N=ϴ(log(1/δ) / ε) 次的實驗就行了~

以上的機率論述我們統稱為 Chernoff Bounds

這東西有什麼有趣的地方呢?讓我們回想一下基於隨機挑選衛兵 (pivot) 的快速排序法。傳統的證明僅能利用期望值的線性組合性質,得出快速排序法的期望遞迴深度是 O(log n),這個會導出快速排序法的期望時間複雜度是 O(n log n)。但我們可以利用 Chernoff Bounds 證明「有很高的機率,該演算法執行時所有遞迴深度都不超過 24 log n」,而這個很高的機率是至少 1 - 1/n^2,很酷吧!


上一篇
Day 19: 線剩計算模型(六)Online Algorithms, Part 6 -- 競爭力分析
下一篇
Day 21: 串流計算模型(一)Streaming Model, Part 1
系列文
當傳統演算法遇到新的計算模型21

尚未有邦友留言

立即登入留言