[Algo] 9.1 Minimum and maximum

定義
order statistic:
The ith order statistic of a set of n elements is the ith smallest element.
minimum:
The minimum of a set of elements is the first order statistic (i = 1).
maximum:
The maximum is the nth order statistic (i = n).
lower median:
$i = \lfloor (n + 1)/2 \rfloor$
For simplicity, we consistently use the phrase "the median" to refer to the lower median.
upper median:
$i = \lceil (n + 1)/2 \rceil$


到底要做過幾次 comparison 才能知道誰是 minimum？

@{
\proc{Minimum}(A)
\li min = A[1]
\li \For i = 2 \;\textbf{to}\;\textit{length}[A]
\li \;\;\;\;\If min > A[i]
\li \;\;\;\;\;\;\;\;min = A[i]
\li \Return min
}@

Lower bound: n-1 comparisons
對任何一個演算法來講，決定誰是 minimum 就像一場巡迴賽一樣。想像每一次 comparison 都是一場比賽，兩者中比較小的為獲勝者，每一場比賽都會有一個輸家。除了 minimum 這個人之外，其他每個人一定曾經輸過一場比賽，所以總共至少會有 n-1 場比賽(因為每一個人都要輸過一場比賽嘛)，也就是至少會有 n-1 次 comparison。


Simultaneous minimum and maximum
用一個 $\Theta(n)$ 的演算法在一個 array 裏，同時找出 minimum 和 maximum 並不難。但是其實"最多"只要 $3\lfloor n/2 \rfloor$ 次的 comparison 就足夠了。

@{
\proc{Simultaneous-Min-Max}(A)
\li \If \;\textit{length}[A]\;\textup{is odd}
\li \;\;\;\;max\;\textup{and}\;min\;\textup{are initialized to}\;A[1]
\li \Else
\li \;\;\;\;max\;\textup{and}\;min\;\textup{are initialized by comparing}\;A[1]\;\textup{and}\;A[2]
\li i = 2
\li \While i + 1 \leq \textit{length}[A]
\li \;\;\;\;M = \textup{the larger of}\;A[i]\;\textup{and}\;A[i+1]
\li \;\;\;\;m = \textup{the smaller of}\;A[i]\;\textup{and}\;A[i+1]
\li \;\;\;\;\If M > max
\li \;\;\;\;\;\;\;\;max = M
\li \;\;\;\;\If m < min
\li \;\;\;\;\;\;\;\;min = m
\li \;\;\;\;i = i + 2
\li \Return max \;\textup{and}\;min
}@



我們來分析一下這個演算法的複雜度，
(1) 如果 n 是奇數，那 min 跟 max 都被初始為 A[1]，接下來每兩個就先做一次 comparison，比較大者就去跟 max 作 comparison，比較小的就去跟 min 作 comparison，所以每一對 A[i] 和 A[i+1] 都會有 3 次 comparison，所以會有 $3 \times (n-1)/2 = 3\lfloor n/2 \rfloor$ 次的 comparison。
(2) 如果 n 是偶數，A[1] 跟 A[2] 先做一次 comparison，那 min 跟 max 先依照 A[1] 跟 A[2] 比較的結果被初始，接下來每兩個就做一次 comparison，道理跟上面差不多。所以每一對 A[i] 和 A[i+1] 都會有 3 次 comparison，所以會有 $3 \times (n-2)/2 + 1 = 3(n/2) - 2 \leq 3\lfloor n/2 \rfloor$ 次的 comparison。