Algorithm Chapter 9 - Medians and Order Statistics

Terminology

第
$k$ 順序統計量 (
$k$ -th order statistic): 在一個大小為
$n$ 的集合中第
$k$ 小的元素
- 最小值 (minimum)：第一順序統計量
- 最大值 (maximum)：第
  $n$ 順序統計量
- 中位數 (median)：整個集合當中在正中央的位置的元素
  - 如果
    $n$ 是奇數，則中位數只有一個，
    $k = \frac{n + 1}{2}$
  - 如果
    $n$ 是偶數，則中位數有兩個，分別為
    $k = \frac{n}{2}$ 和
    $k = \frac{n}{2} + 1$
  - 在排序或是選擇問題中，我們所說的「中位數」是指比較小的那個
  - 在統計學中，中位數指的是中間兩個數加起來的平均

The Selection Problem

item selection(set A, index i)
- Input: 集合
  $A$ （由
  $n$ 個相異元素組成），以及整數
  $i$ （
  $1 \leq i \leq n$ ）
- Output:
  $A$ 當中的某個元素
  $x$ ，其值正好大於
  $i - 1$ 個
  $A$ 當中的其它元素，即第
  $i$ 小的元素

Comparison-based Selection

可以在
$O (n l g n)$ 的時間內解決
- 將
  $n$ 個元素排序，並取出排序好的陣列當中的第
  $i$ 個
- 由於排序演算法的時間複雜度上限在
  $O (n l g n)$ ，所以選擇問題的上限也在
  $O (n l g n)$

只找最大值或最小值，可以在

O (n)

時間內解決

將第一個元素設定為最大 / 最小值
往後一個一個看，如果比目前的極值更大 / 更小，則更新極值
完成
$n - 1$ 次比較後即可獲得最大 / 最小值
時間複雜度為
$T (n) = n - 1$ ，屬於
$O (n)$ 時間








function minimum(A, n) {
    let min = A[0];
    for(let i = 1; i < n; ++i) {
        if(min > A[i]) min = A[i];
    }
    return min;
}
// To find maximum: change > to <

同時找最大值和最小值，也可以在

O (n)

時間內達成

簡單版：執行上面的程式兩次，
$T (n) = 2 n + 2$

進階版：可以在

T (n) = 3 \times ⌊ \frac{n}{2} ⌋

之內找到

若
$n$ 為偶數，比較前兩個元素，將最大值設為較大者，最小值設為較小者
若
$n$ 為奇數，最大值和最小值設為第一個元素
往後每兩個元素一數，互相比較取得較大者和較小者
比較最大值和較大者，並取其中較大的值為最大值
比較最小值和較小者，並取其中較小的值為最小值
比完所有的元素後，即同時取得最大值和最小值
每兩個元素為一組，共
$⌊ \frac{n}{2} ⌋$ 組，每一組只需要比較三次，時間複雜度大約為
$T (n) = 3 \times ⌊ \frac{n}{2} ⌋$
























function maxAndMin(A, n) {
    let max, min;
    if(n % 2 == 0) {
        max = A[0] > A[1] ? A[0] : A[1];
        min = A[0] === max ? A[1] : A[0];
        for(let i = 2; i < n; i += 2) {
            let bigger = A[i] > A[i + 1] ? A[i] : A[i + 1];
            let smaller = A[i] === bigger ? A[i + 1] : A[i];
            max = bigger > max ? bigger : max;
            min = smaller < min ? smaller : min;
        }
    }
    else {
        max = A[0];
        min = A[0];
        for(let i = 1; i < n; i += 2) {
            let bigger = A[i] > A[i + 1] ? A[i] : A[i + 1];
            let smaller = A[i] === bigger ? A[i + 1] : A[i];
            max = bigger > max ? bigger : max;
            min = smaller < min ? smaller : min;
        }
    }
    return {max, min};
}

Randomized Selection

使用隨機搜尋法，可以以平均時間複雜度的期望值在

O (n)

內的時間找到任意第

i

小的元素

利用隨機快速排序法當中的 RANDOMIZED-PARTITION 函數取得隨機的 pivot 值，並且把 input 的陣列分成比 pivot 大和比 pivot 小的兩邊
若隨機回傳的 pivot 值 index 已經等於
$i$ 了，則完成搜尋
若隨機回傳的 pivot 值 index 小於
$i$ ，則遞迴往左半邊的陣列搜尋第
$i$ 小的值
若隨機回傳的 pivot 值 index 大於
$i$ ，則遞迴往右半邊的陣列搜尋第
$i - k$ 小的值（因為已經確定有
$k$ 個值比
$i$ 小，所以在右邊的陣列當中的第
$i - k$ 小的值就是完整陣列中的第
$i$ 小的值）
遞迴直到 pivot 為第
$i$ 小的數字或是 subarray 的大小為 1
最差的時間複雜度可高達
$O (n^{2})$ （理由同快速排序法），但平均時間複雜度的期望值落在
$O (n)$ 當中，算是很迅速的搜尋演算法



































// p = first index in subarray, r = last index in subarray
function randomized_select(A, p, r, i) {
    if(p === r) {
        return A[p];
    }

    let q = randomized_partition(A, p, r); // pivot index in array A
    let k = q - p + 1; // pivot index in this subarray

    if(i === k) {
        return A[q];
    }
    else if (i < k) {
        return randomized_select(A, p, q - 1, i);
    }
    else {
        return randomized_select(A, q + 1, r, i - k);
    }
}

function partition(A, p, r) {
    let random = Math.floor(Math.random() * r + 1);
    swap(A, random, r);
    let pivot = A[r];
    let q = p;

    for (let i = p; i < r; ++i) {
        if (A[i] <= pivot) {
            swap(A, q, i);
            q++;
        }
    }
    swap(A, r, q);
    return q;
}

時間複雜度分析：不知道在工三小（。

Median of Medians

使用 Median of Medians 搜尋法，可以在最差時間複雜度為

O (n)

的情況下找到任意第

i

小的數字

將 input 的陣列五個五個一數，共可分成
$⌈ \frac{n}{5} ⌉$ 組（最後一組可能不滿五個）
用任意一種排序演算法（通常用泡沫排序或插入排序，因為比較好寫）將五個數字排序，並且挑出當中的中位數。因為每一組都只有五個數字，所以每一組要挑出中位數所花的時間是
$O (1)$
總共會挑出
$⌈ \frac{n}{5} ⌉$ 個中位數，遞迴進行上面的步驟直到挑出這
$⌈ \frac{n}{5} ⌉$ 個中位數的中位數
呼叫快速排序法當中的 PARTITION 函數，並且以這個中位數們的中位數為 pivot，將 input 陣列分成兩邊
若 pivot 值 index 已經等於
$i$ 了，則完成搜尋
若 pivot 值 index 小於
$i$ ，則遞迴往左半邊的陣列進行搜尋
若 pivot 值 index 大於
$i$ ，則遞迴往右半邊的陣列進行搜尋
遞迴直到找到第
$i$ 小的元素或是 subarray 的長度為 1



































































function medianOfMedians(A, left, right, i) {
    while(true) {
        if(left === right) {
            return A[left];
        }

        let pivotIndex = pivot(A, left, right);
        pivotIndex = partition(A, left, right, pivotIndex);
        if(i === pivotIndex) {
            return A[pivotIndex];
        }
        else if(i < pivotIndex) {
            right = pivotIndex - 1;
        }
        else {
            left = pivotIndex + 1;
        }
    }
}

function pivot(A, left, right) {
    if(right - left < 5) {
        return insertion_sort(A, left, right);
    }

    for(let i = left; i <= right; i += 5) {
        let subRight = i + 4;
        if(subRight > right) {
            subRight = right;
        }

        let median5 = insertion_sort(A, i, subRight);
        swap(A[median5], A[left + Math.floor((i - left) / 5)]);
    }

    return medianOfMedians(A,
                           left,
                           left + Math.floor((right - left) / 5),
                           left + Math.floor((right - left) / 10));
}

function partition(A, left, right, pivotIndex) {
    let pivotValue = A[pivotIndex];
    swap(A[pivotIndex], A[right]);

    let storeIndex = left;
    for(let i = left; i < right; ++i) {
        if(A[i] < pivotValue) {
            swap(A[storeIndex], A[i]);
            storeIndex++;
        }
    }
    swap(A[storeIndex], A[right]);
    return storeIndex;
}

function insertion_sort(A, left, right) {
    let i, j, tmp;
    for(i = left + 1; i <= right; ++i){
        let tmp = A[i];
        for(j = i; j > left && A[j - 1] > tmp; j--) {
            A[j] = A[j - 1];
        }
        A[j] = tmp;
    }
    return left + Math.floor((right - left) / 2);
}

時間複雜度證明：
- 將 input 的陣列五個五個一數：
  $O (n)$
- 將五個一組的數字排序，並且挑出當中的中位數：
  $O (1) \times ⌈ \frac{n}{5} ⌉ = O (n)$
- 遞迴進行直到挑出這
  $⌈ \frac{n}{5} ⌉$ 個中位數的中位數：
  $T (⌈ \frac{n}{5} ⌉)$
- 呼叫快速排序法當中的 PARTITION 函數將 input 陣列分成兩邊：
  $O (n)$
- 遞迴直到找到第
  $i$ 小的元素：
  $T (7 \times \frac{n}{10} + 6)$
  - 在第 2 步排序完的結果當中，每一組都至少有兩個元素是小於 pivot 的
  - 在第 4 步 partition 完之後，每一個在 pivot 組之前的組，都貢獻了三個比 pivot 小的數字（同理，在 pivot 之後的組都貢獻了三個比 pivot 大的），除了不滿五個元素的組和 pivot 組自己
  - 不考慮最後那兩組的話，總共至少會有
    $3 \times (⌈ \frac{1}{2} \times ⌈ \frac{n}{5} ⌉ ⌉ - 2) \geq 3 \times \frac{n}{10} - 6$ 的數字比 pivot 小 / 大
  - 換句話說，當我們遞迴呼叫 medianOfMedians 的時候，頂多只會處理
    $n - (3 \times \frac{n}{10} - 6) = 7 \times \frac{n}{10} + 6$ 個數字而已，所以最後一步的複雜度是
    $T (7 \times \frac{n}{10} + 6)$
- 寫出遞迴式
  $T (n) = {\begin{cases} O (1), if n < 140 \\ T (⌈ \frac{n}{5} ⌉) + T (7 \times \frac{n}{10} + 6) + O (n), if n \geq 140 \end{cases}$
- （然後就看不懂ㄌ（幹
- 總之最後，
  $T (n) = O (n)$ ，所以這是線性的搜尋演算法

Note

General 的排序演算法，因為其決策樹的長相，決定了任意的排序演算法都至少得花
$Ω (n l o g_{2} n)$ 的時間才能完成排序
線性時間的排序演算法對其 input 的定義域有一定要求，不能排序所有的實數
線性時間的搜尋演算法不倚靠排序，所以才能逃脫
$Ω (n l o g_{2} n)$ 的限制
且線性時間的搜尋演算法對 input 的定義域沒有限制，可以對任意的 input 序列做搜尋

Algorithm Chapter 9 - Medians and Order Statistics

Terminology

The Selection Problem

Comparison-based Selection

Randomized Selection

Median of Medians

Note

Read more

APCS 觀念題 - 運算式

Computer Networking — 2.7 Socket Programming: Creating Network Applications

Computer Networking — 3.1 Introduction and Transport-Layer Services

Computer Networking — 2.4 DNS — The Internet’s Directory Service