計算機演算法 Chapter 9 中位數與順序統計量

第一節 最小值與最大值

單獨求最小值

最直覺的方法：遍歷整個陣列，持續更新目前的最小值

1
2
3
4
5
6

MINIMUM(A)
    min ← A[1]
    for i ← 2 to length[A]
        do if min > A[i]
              then min ← A[i]
    return min

需要 $n - 1$ 次比較，每個元素至少要被比對一次，因此下界就是 $n - 1$，時間複雜度為 $\theta(n)$

同時求最小值與最大值

要同時求最小值與最大值，可以分別跑一次 (各 $n-1$ 次，共 $2(n-1)$ 次比較)，但實際上不需要如此麻煩

<註1> $n$ 為偶數：這裡可以用 $n - 2$ 的原因是因為我們一開始可以直接取出前兩個比較一次後分別當 max / min，這也解釋了為甚麼後面要 $ + 1$
<註2> $n$ 為奇數：取出第一個元素同時當 max / min，因此是 $3\lfloor n/2 \rfloor$

第二節 Randomized Select

問題定義

Pseudocode

RANDOMIZED-SELECT 的核心概念借用 Quick Sort 的 PARTITION，但是是隨機取 pivot 的 RANDOMIZED-PARTITION，但它只遞迴進入一側（因為只需要找第 $i$ 小，另一側無需處理），這邊 PARTITION 的內容在第七章講 Quick Sort 的地方有詳細說明，這裡不再贅述

1
2
3
4
5
6
7
8

PARTITION()
    x ← A[r]
    i ← p - 1
    for j ← p to r - 1
        do if A[j] ≤ x
            then i ← i + 1
                 exchange A[i] ↔ A[j]
    exchange A[i+1] ↔ A[r]

1
2
3
4

RANDOMIZED-PARTITION(A, p, r)
    i ← RANDOM(p, r)
    exchange A[r] ↔ A[i]
    return PARTITION(A, p, r)

1
2
3
4
5
6
7
8
9
10

RANDOMIZED-SELECT(A, p, r, i)
    if p = r
        then return A[p]                               # 只剩一個元素，直接回傳
    q ← RANDOMIZED-PARTITION(A, p, r)
    k ← q - p + 1                                     # k = pivot 在 [p..r] 中的排名
    if i = k
        then return A[q]                               # pivot 正好是第 i 小
    elseif i < k
        then return RANDOMIZED-SELECT(A, p, q - 1, i) # 第 i 小在左半部
    else return RANDOMIZED-SELECT(A, q + 1, r, i - k) # 第 i 小在右半部

說明

做完 RANDOMIZED-PARTITION 之後，pivot 被放到位置 $q$，此時：

• $A[p..q-1]$ 的所有元素都 $\le A[q]$（順序不重要，只知道都比 pivot 小）
• $A[q+1..r]$ 的所有元素都 $> A[q]$（順序不重要，只知道都比 pivot 大）
• $k = q - p + 1$ 代表 pivot 是 $A[p..r]$ 中第 $k$ 小的元素

第三節 線性時間求法

動機

雖然 RANDOMIZED-SELECT 的期望值是 $\Theta(n)$，但最壞情況仍是 $\Theta(n^2)$，問題就在於 RANDOMIZED-SELECT 不能保證求到足夠靠近中位數的值。若需要保證最壞情況也是線性時間，必須使用確定是線性時間的 SELECT 演算法

Pseudocode

1
2
3
4
5
6
7
8
9
10
11

SELECT(A, start, end, i)         /* 找第 i 小的元素 */
1. 將 A[start..end] 分成 ⌈n/5⌉ 組，每組最多 5 個元素
2. 對每組用 insertion sort 排序，並取出各組的中位數
3. 遞迴呼叫 SELECT 找出「各組中位數」中的中位數 x
4. 以 x 為 pivot，對 A[start..end] 執行 PARTITION，得到 pivot 位置 k
5. if i = k
        return x
    else if i < k
        return SELECT(A, start, pivot-1, i)
    else
        return SELECT(A, pivot+1, end, i - (pivot - start + 1))

為何 Pivot 保證「夠好」的切割？

（圖片來源：Introduction to Algorithms, 2nd ed., Figure 9.1）

圖片中每一欄代表一組（5 個元素）。白色節點是各組的中位數，被圈起來標記的 $x$ 是中位數的中位數。箭頭從大元素指向小元素

至少有一半的中位數 $\ge x$，而只要中位數 $\ge x$，就代表那一組內還有 $\ge 3$ 個元素比 $x$ 大。這需要扣除掉 $x$ 自己那組與不滿 5 人的最後一組，因此我們可以確定：

$$\text{至少有 } \left\lceil \frac{1}{2} \cdot \frac{n}{5} \right\rceil \cdot 3 - 6 \ge \frac{3n}{10} - 6 \text{ 個元素} > x$$

同理，也至少有 $\frac{3n}{10} - 6$ 個元素 $< x$。因此，在最壞情況下，另一邊較大的子問題規模為：

$$n - \left(\frac{3n}{10} - 6\right) = \frac{7n}{10} + 6$$

時間複雜度分析

遞迴式為：

$T(n) = T!\left(\frac{n}{5}\right) + T!\left(\frac{7n}{10} + 6\right) + O(n)$

代換法（Substitution Method）：
(這邊在第四章有詳細說明步驟)

猜測 $T(n) \le cn$，驗證：

$T(n) \le c\cdot\frac{n}{5} + c\left(\frac{7n}{10} + 6\right) + O(n)$
$= c\cdot\frac{n}{5} + \frac{7cn}{10} + 6c + O(n)$
$= cn - \frac{cn}{10} + 6c + O(n)$
$\le cn \quad \text{（當 } n \ge 80 \text{ 且 } c \text{ 足夠大，例如 } c = 200\text{）}$

因此 SELECT 的時間複雜度為 $\Theta(n)$，最壞情況也是線性時間。

<註> 此方法亦可摘取部分步驟作為 Quick Sort 的 PARTITION，可將 Quick Sort 的 worst case 從 $O(n^2)$ 降為 $O(n \lg n)$

總結

參考文獻

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, Second Ed., The MIT Press, 2001.