Select k-th element in linear time

上週日提起 linear time 的 selection algorithm, 發現 wiki 寫得很詳細
原理很簡單, 只是原本 partial quick sort 選 pivot 的那部份改進

假設 PICK(A, k) = k-th element in A[]
原本是 random 選一個 pivot, 現在則是把 array A 分成 |A|/5 組
每組找出 5 個數中的 median, 叫作 B[0], B[1], .. B[|A|/5-1]

然後 call PICK(B, |B|/2) recursive 找出 B[] 真正的 median 作為 pivot
由於每個 B[i] 都至少大於/等於 3 個 element, 而 pivot 又大於/等於 |A|/10 個 B[] 中的數
所以 pivot 至少大於/等於(& 小於/等於) A 中 3/10 的 element, 即是 partition 後的 size 最大為原本的 7/10
然後便像原本 partial quick sort 做下去

得 T(N) = T(N/5) + T(7N/10) + O(N)
⇒ T(N) = c * N * (1 + 9/10 + 81/100 + ...) ≤ 10 * c * N = O(N)

一開始覺得 '5' 很神奇, 發現其實不一定要是 5
假設不是分為 |A|/5 組而是 |A|/k 組 (k = odd integer)
便會變成

T(N) = T(N/k) + T(N * (1 - (k+1)/4k)) + O(N)

T(N) 是 linear 的條件是 1/k + (1 - (k+1)/4k) < 1 即 k > 3
估計由於 5 是最小的 odd integer solution 所以是 5 吧 [利申: 我估的]