[筆記] 線性時間內尋找中位數 (Median of Median)

要找一串未排序數字的中位數 (或者更廣泛一點，第 k 小的數字)，最簡單的方法自然就是先排序後再找出來，當然，這種方法就會受限於排序演算法的複雜度，一般情況而言，最糟情況下會是 O(n log n)。不過因為我們在意的其實只有第 k 小的數字，所以就有人想辦法弄出了線性時間的演算法，這方法好像沒有明確的名稱，大抵上是利用 divide & conquer 的概念來做的，再加上原先是設計用來找中位數的，所以 google 的話可以用 Median of Median 當關鍵字來找。另外其實也有許多不同的方法，各有優缺點，可以依照實際應用情況來決定怎麼設計。

其實 GeeksforGeeks 上有一篇文章有談到幾種比較好實作的替代方案了。簡單歸納如下：

• 直接 sort：最簡單省事的方法，除非真的是對效能很敏感的狀況，不然我覺得與其使用其他方法不如直接排序比較快
• 利用 min heap / max heap：要用哪種 heap 要看 k 跟 n 的大小。簡單來說概念就是利用 heap 只保存 k 個數字，要找第 k 小就用 max heap；反之，要找第 k 大就用 min heap。
• Quick Select：稍微改變 quick sort 的方法，選出 pivot 後只對包含第 k 小的數字的那一組遞迴下去處理。 
• C++ STL 有 std::nth_element 可以用

以上的方法，除了 sort 之外，實際使用上的平均複雜度其實也接近線性時間，但最差情形當然不是。特別是 quick select 會跟 quick sort 一樣遇上 pivot 選得不好會很慘。所以其中一個改良的方法就是利用 Median of Median 在線性時間內找出中位數，再利用中位數當 pivot 來運作 quick select 就能在線性時間內完成目標。

**************************************************************************
更新：median of median 找出來的中位數不是真的中位數，只是一個近似的中位數。median of median 的目的只是讓 quick select 有個較好的 pivot 可以讓理論複雜度降低而已。
**************************************************************************

Median of Median 概念說穿了不難，先把原始的數字每 5 個一組，各自找出每一組的中位數，再把這些中位數蒐集起來，把相同的概念遞迴的套用下去，直到最後剩下一個數字就是中位數囉。Median of Median 最大的問題其實是出在他的常數項頗大，因此雖然理論複雜度是線性時間，不過實際運用起來不見得能比上面的那幾個方法好到哪去。

至於為什麼 Median of Median 是 5 個為一組...雖然實際原因要去找原始論文才知道，不過個人猜測只是妥協 XD

另外 STL 的 nth_element 時間複雜度寫的不是最差情況而是平均情況，所以應該不是 Median of Median，而是類似 quick select 的概念，不過這也不是訂死的就是，所以應該還是要看怎麼實作的。