[Algo] 9.2 Selection in expected linear time

RANDOMIZED-SELECT(A, p, r, i)

1  if p == r

2    then return A[p]

3  q = RANDOMIZED-PARTITION(A, p, r)

4  k = q - p + 1

5  if i == k

6    then return A[q]

7  else if i < k

8    then return RANDOMIZED-SELECT(A, p, q-1, i)

9  else

10   return RANDOMIZED-SELECT(A, q+1, r, i-k)

RANDOMIZED-PARTITION 我們在 [Algo]7.3 就已經看過了。我們接下來先分析一下 RANDOMIZED-SELECT。一開始 A[q] 被當作 pivot，因為我們知道 A[q+1 .. r] 裏面的所有 item 都比 A[q] 還要來的大，所以如果我們要挑的 ith order statistic 比 A[q] 小的話，那我們就去 A[p..q-1] 裏面挑，否則的話我們就去 A[q+1..r] 裏面挑。不同於 quicksort，它是 partition 完之後左右兩邊都要繼續遞迴下去，這裡只有一邊會繼續遞迴下去。
RANDOMIZED-SELECTION 的 average-case 是 $\Theta(n)$，worst-case 是在我們每次都很晦氣的只把 A[p..r] 分成一邊為 n-1，另一邊為 1 的狀況，這個時候我們的複雜度就是 $\Theta(n^2)$，這樣即使只是要找 minimum 或 maximum 都很不划算。但是因為這個演算法是 randomized 的，所以沒有任何一種特殊的 input 會導致到這種 worst-case，除非我們運氣真的非常不好。


running time of RANDOMIZED-SELECTION
$T(n)$：對一個長度為 n 的 array A[p..r] 執行 RANDOMIZED-SELECTION 所要花費的 running time
$X_k$：一個 indicator random variable，定義為：$X_k$ = I{ the subarray A[p..q] has exactly k elements }，因為我們假設 A[p..q] 中每一個 element 被選為 pivot 的機率都一樣，所以 $E[X_k] = 1/n$。
接下來我們要求的是 $E[T(n)]$ 的值。根據演算法，我們可以知道：
$$T(n) \leq \sum_{k = 1}^n X_k\cdot(T(\max(k-1, n-k)) + O(n))$$
$$E[T(n)] \leq E[\sum_{k = 1}^n X_k\cdot(T(\max(k-1, n-k)) + O(n))]$$
$$= \sum_{k = 1}^n E[X_k\cdot(T(\max(k-1, n-k))] + O(n)$$
$$= \sum_{k = 1}^n E[X_k]\cdotE[T(\max(k-1, n-k))] + O(n)$$ ($X_k$ 跟 $T(\max(k-1, n-k))$ 是彼此獨立的)
$$= \sum_{k = 1}^n \frac{1}{n}\cdotE[T(\max(k-1, n-k))] + O(n)$$
在 $k > \lceil n/2 \rceil$ 的時後，$\max(k-1, n-k) = k-1$，在 $k \leq \lceil n/2 \rceil$ 的時候，$\max(k-1, n-k) = n-k$。當 n 是偶數的時候從 $T(\lceil n/2 \rceil)$ 到 $T(n-1)$ 都會重複兩次，當 n 是奇數的時候，除了 $T(\lfloor n/2 \rfloor)$ 只出現過一次之外，其他每一項都會出現兩次，所以我們可以知道：
$$E[T(n)] \leq \frac{2}{n}\sum_{k=\lfloor n/2 \rfloor}^{n-1}E[T(k)] + O(n)$$

接下來，我們用 substitution method 來解這個遞迴式，假設 $T(n) \leq cn$，其中 c 為一個常數。再假設 $O(n)$ 這一項被 $an$ 給 bound 住，其中 a 為一個常數。
$$E[T(n)] \leq \frac{2}{n}\sum_{k=\lfloor n/2 \rfloor}^{n-1}ck + an = \frac{2c}{n}(\sum_{k = 1}^{n-1}k - \sum_{k = 1}^{\lfloor n/2 \rfloor - 1}k) + an$$
$$= \frac{2c}{n}(\frac{(n-1)n}{2} - \frac{(\lfloor n/2 \rfloor -1)\lfloor n/2 \rfloor}{2}) + an \leq \frac{2c}{n}(\frac{(n-1)n}{2} - \frac{(n/2 -2)(n/2 - 1)}{2}) + an$$
$$=\frac{2c}{n}(\frac{n^2 - n}{2} - \frac{n^2/4 - 3n/2 + 2}{2}) + an = \frac{c}{n}(\frac{3n^2}{4} + \frac{n}{2} - 2) + an$$
$$=c(\frac{3n}{4} + \frac{1}{2} - \frac{2}{n}) + an \leq \frac{3cn}{4} + \frac{c}{2} + an = cn - (\frac{cn}{4} - \frac{c}{2} - an)$$
為了要完成這個證明，我們要保證$cn/4 - c/2 - an \geq 0$ 在 n 足夠大的時候。
$$\frac{cn}{4} - \frac{c}{2} - an \geq 0 \Rightarrow n(c/4 - a) \geq c/2$$
為了要讓它大於 0，所以 $c > 4a$，此時
$$n \geq \frac{c/2}{c/4-a} = \frac{2c}{c-4a}$$
所以只要我們假設在 $n < 2c/(c-4a)$ 的時候 $T(n) = O(1)$，我們就可以得到 $T(n) = O(n)$