中位數的比較下界（comparison lower bound for the median）

中位數的中位數演算法在最壞情況下用 O(n) 次比較找出中位數（或任意第 k 小）——令人驚訝的是，你「不必」排序，否則要花 n log n。一個公平的問題是：中位數究竟最少需要多少次比較？下界說中位數選取至少需要線性次數的比較，Omega(n)——事實上嚴格「多於」只找最大值所需的 n-1 次。找中間可證明地比找極值難，儘管兩者都是線性。

下界容易的那一半是一個乾淨的對手觀察：要正確報出中位數，演算法尤其必須「看過」每個元素——任何它從未比較過的元素都可能暗地裡是任何值，包括一個會改變誰是中位數的值。所以光是要讓每個人都參與，就至少需要 n-1 次比較，與最大值同一塊地板。有趣的那一半是中位數嚴格需要更多。對手論證顯示演算法在過程中必須有效地證明約 n/2 個元素在中位數之下、n/2 個在其上，而認證兩側會在「碰到每個元素」之外逼出額外的比較。已知對精確中位數最好的下界約為 2n 次比較，而最佳演算法用常數乘以 n；釘死那個精確常數是一個著名且仍懸而未決的細粒度問題。

誠實的結論。第一，Omega(n) 在「數量級」上是緊的：線性時間選取（中位數的中位數）達到 O(n)，所以這問題是 Theta(n) 次比較——你絕不必為了找一個順序統計量而付出完整排序的 n log n。第二，精確的常數倍真的很微妙、尚未完全解決，提醒我們「知道它是線性」不等於「知道它的確切值」。第三，這是比較模型的陳述；實用的中位數的中位數是線性的，但帶有比快速選取更大的隱藏常數，而快速選取的期望時間是 O(n)、最壞情況卻是 O(n^2)。