Day-18 BFPRT演算法

2021 iThome 鐵人賽

DAY 18

自我挑戰組

從0開始啃Introduction of algorithms心得與記錄系列第 18 篇

13th鐵人賽自學筆記 algorithm

吳他，惟手熟爾

2021-09-29 11:26:12

1387 瀏覽

分享至

最壞情況為 $\Theta(n)$ ，BFPRT演算法

在由隨機數決定陣列的分割的情況下，我們如何避免產生出最差情況(雖然出現的機率很小)，或是讓最差的情況時間複雜度也是 $\Theta (n)$ 。

BFPRT演算法(由 Blum, Floyd, Pratt, Rivest 與 Tarjan 創造)可以實現出這一件事情，這是一個具有確定性(deterministic)的演算法，也就是不含任何隨機的成分。

我們會產生出最差的情況為分割極度不平衡，也就是產生出 $0:n-1$ 這種分割，而會產生出這種分割，和我們的主元(pivot)的選擇很有關係，如果我們可以保證選擇到的主元(pivot)都是好的，確保不會產生出最差分割，這個主元是確定是最好的，也就是在樣本空間無限大時，每一次的主元都是好的，而不是機率上趨近於最好。那麼這個演算法就可以避免掉最差情況的發生。而這就是BFPRT演算法的主要想法。

BFPRT演算法遵循以下五個步驟

將n個元素的 $A$ 陣列(不一定要是陣列)拆分成 ${\lfloor}n/5{\rfloor}$ 組，每一組含有5個元素，最後一組由 $n\ {mod}\ 5$ 組成，如果 $n=1$ ，則直接回傳 $A[n]$ 。
尋找這 ${\lceil}n/5{\rceil}$ 組中每一組的中位數，方法為對每一組元素使用insertion sort，排序後找出中位數，每一組都有五個元素，因此經過排序後地三個元素即為中位數。
在2.中會找出 ${\lceil}n/5{\rceil}$ 個中位數，把這些中位數也組成一個陣列，在這個陣列中找到中位數 $x$ (透過遞迴呼叫BFPRT)。
在3.產生出由中位數產生的陣列，以 $x$ 作為主元(pivot)對陣列進行劃分。比 $x$ 小的元素劃分到 $x$ 的左邊， $x$ 本身被劃分到左邊，而比 $x$ 大的元素劃分到左邊。
將 $k$ 定義為 $k = rank(x)$ ，也就是將 $k$ 當作 $x$ 在陣列中大小的排名，而輸入的參數 $i$ 表示我們要尋找陣列中第 $i$ 大的元素。
如果 $i=k$ ，則直接回傳 $x$ 。
如果 $i < k$ ，則在陣列中左分割的部分，也就是比 $x$ 小的部分遞迴呼叫BFPRT
如果 $i > k$ ，則在陣列中右分割的部分，也就是比 $x$ 大的部分遞迴呼叫BFPRT

範例 : 輸入一個有34個元素的A陣列， $A[34]$

將n個元素的 $A$ 陣列拆分成 ${\lfloor}n/5{\rfloor}$ 組，每一組含有 $5$ 個元素，最後一組由 $n\ {mod}\ 5$ 個元素組成。
尋找這 ${\lceil}n/5{\rceil}=7$ 組中每一組的中位數
在2.中會找出 ${\lceil}n/5{\rceil}=8$ 個中位數，把這些中位數也組成一個陣列，在這個陣列中找到中位數 $x$ (透過遞迴呼叫BFPRT)。
在3.產生出由中位數產生的陣列，以 $x$ 作為主元(pivot)對陣列進行劃分。比 $x$ 小的元素劃分到 $x$ 的左邊， $x$ 本身被劃分到左邊，而比 $x$ 大的元素劃分到左邊。

$x$ 的排名為第3名，令 $k=rank(x)$ ，中位數組成的子陣列有7個元素， $n=7$ ，右邊的分割有 $n-k=4$ 個元素，左邊分割有 $n-k-1=3$ 個元素
接著通過遞迴呼叫找到我們要的元素

我們把上面這個陣列看作是一張圖(graph)，我們在兩個節點(或是元素)定義以下符號，表示 $a < b$

我們把這樣的符號，加到上面的圖上

我們也對中位數構成的子陣列加上這樣的符號

得到這張非常混亂，~~就像是我的麵包版的圖~~

我們使用箭頭，表示是一個有向路徑，也就是我們走訪的路線，我們可以透過任一條路徑，得知兩個元素之間的大小關係，且通過這個路徑，我們可以知道陣列每一個區塊和 $x$ 之間的關係。

由箭頭我們可以知道 $a < b$ ， $b < x$ ，因此 $a < x$ ， $a$ 上面的元素也必定小於 $x$ ，旁邊的分組也是如此，因此我們可以知道，灰色區域框住的陣列區塊中所有元素皆小於等於 $x$

而橘色部分中所有元素，必定大於等於 $x$

由上面這張圖我們可以知道，每一個分組中有 $https://chart.googleapis.com/chart?cht=tx&chl=%5Cfrac%203%205$ 的元素會小於等於 $x$ ，而我們將這個含有 $34$ 個元素的陣列拆分成 ${\lfloor}n/5{\rfloor}+1$ 組( $+1$ 為含 $n \ mod\ 5$ 個元素的組)，其中有 ${\lfloor}{\lfloor}n/5{\rfloor}/2{\rfloor}$ 的組會存在 $https://chart.googleapis.com/chart?cht=tx&chl=%5Cfrac%203%205$ 的元素會小於等於 $x$ 這個性質，因此，我們可以推導出以下性質:

給定 $n$ 個元素的 $A$ 陣列 :

$3{\lfloor}{\lfloor}n/5{\rfloor}/2{\rfloor}$ 個元素小於等於 $x$ ，(在由中位數劃分出的子陣列中，有 ${\lfloor}n/5{\rfloor}/2$ 個元素小於等於 $x$ )

而每一個分組中，也至少會有 $https://chart.googleapis.com/chart?cht=tx&chl=%5Cfrac%203%205$ 個元素大於等於 $x$ ，而我們將含有 $34$ 個元素的陣列猜分成 ${\lfloor}n/5{\rfloor}=6+1$ 組，其中有 ${\lfloor}{\lfloor}n/5{\rfloor}/2{\rfloor}+2$ 會具有 $https://chart.googleapis.com/chart?cht=tx&chl=%5Cfrac%203%205$ 的元素大於等於 $x$ 這個性質，

給定 $n$ 個元素的 $A$ 陣列 :

$\displaystyle 3{\lfloor}{\lfloor}n/5{\rfloor}/2+2{\rfloor}$ 個元素大於等於 $x$ ，(在由中位數劃分出的子陣列中，有 ${\lfloor}n/5{\rfloor}/2+2$ 個元素大於等於 $x$ )

BFPRT效率分析

由上面的推論，我們可以得到以下性質

$https://chart.googleapis.com/chart?cht=tx&chl=%5Cdisplaystyle%203%7B%5Clfloor%7D%7B%5Clfloor%7Dn%2F5%7B%5Crfloor%7D%2F2%7B%5Crfloor%7D%20%3E%3D%20%5Cfrac%20%7B3n%7D%20%7B10%7D$ 個元素小於等於 $x$
$https://chart.googleapis.com/chart?cht=tx&chl=%5Cdisplaystyle%203%7B%5Clfloor%7D%7B%5Clfloor%7Dn%2F5%7B%5Crfloor%7D%2F2%20%2B%202%7B%5Crfloor%7D%20%3E%3D%20%5Cfrac%20%7B3n%7D%20%7B10%7D%20%2B%206$ 個元素大於等於 $x$

由上面這個性質我們可以知道，最多我們可以產生出一個 $https://chart.googleapis.com/chart?cht=tx&chl=%5Cdisplaystyle%200%3A%5Cfrac%20%7B3n%7D%20%7B10%7D%20%2B%20%5Cfrac%20%7B3n%7D%20%7B10%7D%20%2B%206$ 個元素的分割情況，為了求上界，我們簡化成最多產生出 $https://chart.googleapis.com/chart?cht=tx&chl=0%3A%5Cfrac%20%7B7n%7D%20%7B10%7D$ 的分割情況，也就是在第5步中，BFPRT遞迴呼叫做多作用在 $https://chart.googleapis.com/chart?cht=tx&chl=%5Cfrac%20%7B7n%7D%20%7B10%7D$ 個元素上。

下面推導BFPRT演算法最壞情況的執行時間 $T(n)$

拆分陣列需要 $O(n)$
固定陣列大小的排序，需要的時間是固定的，因此為 $O(n)$
遞迴呼叫需要 $T({\lfloor}n/5{\rfloor})$
劃分需要 $O(n)$
遞迴呼叫最多需要 $https://chart.googleapis.com/chart?cht=tx&chl=T(%5Cfrac%20%7B7n%7D%20%7B10%7D)$

因此， $T(n)$ 的上限為以下關係式
$https://chart.googleapis.com/chart?cht=tx&chl=%5Cdisplaystyle%20T(n)%3C%3DT(%7B%5Clfloor%7Dn%2F5%7B%5Crfloor%7D)%2BT(%5Cfrac%20%7B7n%7D%20%7B10%7D)%2BO(n)$ ，使用代換法求解

假設 $T(n)<=cn$ ，則
$https://chart.googleapis.com/chart?cht=tx&chl=%5Cdisplaystyle%20T(n)%3C%3DT(%7B%5Clfloor%7Dn%2F5%7B%5Crfloor%7D)%2BT(%5Cfrac%20%7B7n%7D%20%7B10%7D)%2BO(n)$
$\displaystyle \\=1/5*cn+7/10*cn+O(n)$
$\displaystyle \\=9/10*cn+O(n)$
$\displaystyle \\=cn-(1/10*cn-O(n))$ ，如果常數 $c$ 足夠大，則 $(1/10*cn-O(n))$ 為非負的項，觀察可以發現，只要我們 $c$ 取 $10$ 的任意倍數，就可以實現了，而當 $n <= 50$ ，則 $T(n)$ 為 $O(1)$ ，如果 $c$ 足夠大，則 $T(n)$ 的上限就是 $cn$ ，也就是線性時間。