tags: ADA 4.2 Selection Problem

ADA 4.2: Selection Problem 選擇問題 (求第k名)

Textbook Chapter 9.3 - Selection in worst case linear time

What is Selection Problem?

取一有

$n$ 個 integers 的

$arrayA$
求輸出

$arrayA$ 裡第

$k$ 大的數字

Solution 1: Sorting

藉由將陣列

$A$ 重新由小排到大，要第

$k$ 大就直接取第

$k$ 位置的值

但因為用到排序(sort)，所以其時間複雜度落在

$O(nlogn)$

當

$n>>k$ , sorting 的時間複雜度就會越差越多

如何將時間複雜度再往下調呢?

Solution 2: Divide-and-Conquer

想法

• 設定一個基準點(
  $pivot$)，將原本的陣列依基準點拆成兩半
• 若
  $k\le |X_{>}|$，則代表
  $k$ 落在
  $X_{>}$ 裡的第
  $k_{th}$ 位置上
• 若
  $k>|X_{>}|$，則代表
  $k$ 落在
  $X_{<}$ 裡的第
  $(k-|X_{>}|{)}_{th}$ 位置上

我們會希望基準點(

$pivot$)會盡量在中間，因為如果基準點一邊個數太大，若

$k$ 剛好都落在較大的一邊，則最差情況你要拆

$n$ 遍才能找到你要的數值

如何找尋中位數？

• 尋找中位數也是另一個 Selection Problem，只是
  $k$ 為中位數

Step 1: Five Men Per Group

• 將 n 個個數的 array 每5個一組，而會分成總共
  $\frac{n}{5}$ 組，每組因為數量為 constant (5個)，強制sorting所花費的時間為 constant

Step 2: A Median Per Group

• 每組取其中間值(Median)

上圖為取中間值(黃點)而所做 sorting 動作，箭頭代表序列由小變大

Step 3: Median of Medians

• 從
  $\frac{n}{5}$ 組的所有中間值(medians)在做排序取得中間值(median)

上圖將所有medians在做排序在取其中間值(紅點)

在 medians 取得 median 時，若 medians 個數為偶數，通常會取較小的那個值當作 MoM
Reference: Chapter 9.3 p220.第三點

Step 4: Partition via MoM

• 在取得MoM後，將此數作為切割點(pivot)，在
  $MoM$ 的左邊為小於
  $MoM$ 元素的集合
  $X_{<}$，右邊則為大於
  $MoM$ 元素的集合
  $X_{>}$

Step 5: Recursion

接著我們就要判斷

$k$ 位於哪個地方，依照上圖會有三種情況

1. $k$ 落於
   $X_{>}$ 裡面（其 index 一樣落在
   $X_{>}$ 的第
   $k_{th}$ 位置上）
2. $k$ 落於
   $MoM$ 上（index 應為
   $|X_{>}|+1$）
3. $k$ 落於
   $X_{<}$ 裡面（其 index 會落在
   $X_{<}$ 的第
   $(k-|X_{>}|-1{)}_{th}$ 位置上）

這裡的recursion有牽涉兩個地方

1. 找尋
   $MoM$
2. $k$ 落於
   $X_{>}$ 或者
   $X_{<}$，就要再做一次遞迴拆解一次(直到序列夠小可以直接找到
   $k$ 值)

Divide-and-Conquer for Selection Problem

依序拆解各個時間複雜度

• base case:
  $\mathrm{\Theta }(1)$
• divide groups with size 5:
  $\mathrm{\Theta }(1)$
• median from group i:
  $\mathrm{\Theta }(n)$
• MoM:
  $T(\frac{n}{5})$
• case divide:
  $\mathrm{\Theta }(n)$
• case 1:
  $T(|X_{>}|)$
• case 2:
  $\mathrm{\Theta }(1)$
• case 3:
  $T(|X_{<}|)$

我們希望

$|X_{>}|$、

$|X_{<}|$ 的數量盡量不要差距太大(不然 recursive 的次數就越多)
在做 recursion 時可以每次去掉一些元素
以

$k$ 在

$|X_{>}|$、

$|X_{<}|$ 的情況每次可剔除

$\frac{n}{5}÷2\times 3=\frac{3}{10}n$
下回要 recursion 的數量就變為

$\frac{7}{10}n$

Time Complexity

• $T(n)$ = time for running
  $Selection(X,k)$ with
  $|X|=n$

$T(n)=\{\begin{array}{ll}\mathrm{\Theta }(1)& \text{if }n=1\\ T(\frac{n}{5})+max(T(|X_{>}|),T(|X_{<}|))+\mathrm{\Theta }(n)& \text{if }n>1\end{array}$

becomes…

$T(n)=\{\begin{array}{ll}\mathrm{\Theta }(1)& \text{if }n=1\\ T(\frac{9n}{10})+\mathrm{\Theta }(n)& \text{if }n>1\end{array}$

applying Master Method case 3

$T(n)=\mathrm{\Theta }(n)$

applying Sustitution Method

---