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\le i\le n$）
  • Output:
    $A$ 當中的某個元素
    $x$， 其值正好大於
    $i-1$ 個
    $A$ 當中的其它元素，即第
    $i$ 小的元素

Comparison-based Selection

• 可以在
  $O(nlgn)$ 的時間內解決
  • 將
    $n$ 個元素排序，並取出排序好的陣列當中的第
    $i$ 個
  • 由於排序演算法的時間複雜度上限在
    $O(nlgn)$， 所以選擇問題的上限也在
    $O(nlgn)$
• 只找最大值或最小值，可以在
  $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)=2n+2$
  • 進階版： 可以在
    $T(n)=3\times \lfloor \frac{n}{2}\rfloor$ 之內找到
    • 若
      $n$ 為偶數，比較前兩個元素，將最大值設為較大者，最小值設為較小者
    • 若
      $n$ 為奇數，最大值和最小值設為第一個元素
    • 往後每兩個元素一數，互相比較取得較大者和較小者
    • 比較最大值和較大者，並取其中較大的值為最大值
    • 比較最小值和較小者，並取其中較小的值為最小值
    • 比完所有的元素後，即同時取得最大值和最小值
    • 每兩個元素為一組，共
      $\lfloor \frac{n}{2}\rfloor$ 組，每一組只需要比較三次，時間複雜度大約為
      $T(n)=3\times \lfloor \frac{n}{2}\rfloor$
    ​​​​​​​​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 的陣列五個五個一數，共可分成
    $\lceil \frac{n}{5}\rceil$ 組（最後一組可能不滿五個）
  • 用任意一種排序演算法（通常用泡沫排序或插入排序，因為比較好寫）將五個數字排序，並且挑出當中的中位數。因為每一組都只有五個數字，所以每一組要挑出中位數所花的時間是
    $O(1)$
  • 總共會挑出
    $\lceil \frac{n}{5}\rceil$ 個中位數，遞迴進行上面的步驟直到挑出這
    $\lceil \frac{n}{5}\rceil$ 個中位數的中位數
  • 呼叫快速排序法當中的 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 \lceil \frac{n}{5}\rceil =O(n)$
    • 遞迴進行直到挑出這
      $\lceil \frac{n}{5}\rceil$ 個中位數的中位數：
      $T(\lceil \frac{n}{5}\rceil )$
    • 呼叫快速排序法當中的 PARTITION 函數將 input 陣列分成兩邊：
      $O(n)$
    • 遞迴直到找到第
      $i$ 小的元素：
      $T(7\times \frac{n}{10}+6)$
      • 在第 2 步排序完的結果當中，每一組都至少有兩個元素是小於 pivot 的
      • 在第 4 步 partition 完之後，每一個在 pivot 組之前的組，都貢獻了三個比 pivot 小的數字（同理，在 pivot 之後的組都貢獻了三個比 pivot 大的），除了不滿五個元素的組和 pivot 組自己
      • 不考慮最後那兩組的話，總共至少會有
        $3\times (\lceil \frac{1}{2}\times \lceil \frac{n}{5}\rceil \rceil -2)\ge 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{array}{l}O(1)\text{, if }n<140\\ T(\lceil \frac{n}{5}\rceil )+T(7\times \frac{n}{10}+6)+O(n)\text{, if }n\ge 140\end{array}$$
    • （然後就看不懂ㄌ（幹
    • 總之最後，
      $T(n)=O(n)$， 所以這是線性的搜尋演算法

Note

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