演算法

tags: 大學必修-筆記

CH1 Union-Find 演算法

演算法的方法

• Find -> 看 p 這個點在哪裡
• Connected -> 看 p q 兩點是否相連
• Union -> 把 p q 兩點連在一起

quick-find

id[] 裡面存的是，如果數字一樣 -> 同 union

• Find -> 看 p 的 id 是多少
• Connected -> 看 p q 兩點的 id 是否一樣
• Union -> 把 id[p] 的值放到 id[q] 裡

public class QuickFindUF {

    private int[] id; 

    public QuickFindUF(int N) {            // 初使化矩陣

        id = new int[N];
        for (int i = 0; i < N; i++)
            id[i] = i;
    }

    public int find(int p) {               // find 方法
        return id[p]; 
    }
    
    public void union(int p, int q) {      // union 方法

        int pid = id[p];
        int qid = id[q];

        for (int i = 0; i < id.length; i++)  // 把每個 q 變成 p
            if (id[i] == pid) id[i] = qid; 
}

algorithm	initialize	union	find	connected
quick-find	N	N	1	1

quick-union

用 tree 的想法實作
id[] 裡面存的是，這個點的 root(最上面的點) 是誰

• Find -> p 點的 root 是誰
• Connected -> 看 p q 的 root 是否一樣
• Union -> 把 p 的 root 指向 q 的 root

public class QuickUnionUF {

    private int[] id; 

    public QuickUnionUF(int N) {            // 初使化矩陣
        
        id = new int[N];
        for (int i = 0; i < N; i++) 
            id[i] = i;
    }
    
    public int find(int i) {                // 要一直朝root往上找
                                            // 樹有可能好幾層
        while (i != id[i]) 
            i = id[i];
        return i;
    } 

    public void union(int p, int q) {       // 把 p 的 root
                                            // 給 q 的 root
        int proot = find(p);                // 代表兩個樹接在一起
        int qroot = find(q);
        id[proot] = qroot;
    }
}

algorithm	initialize	union	find	connected
quick-find	N	N	1	1
quick-union(worst case)	N	N	N	N

• 最好的情況
• 最壞的情況

weighted QU

• 在 union 的過程中有可以小樹接在大樹上
• 會把 tree height 變高
• 改量方法為永遠是 大樹接小樹

algorithm	initialize	union	find	connected
quick-find	N	N	1	1
quick-union(worst case)	N	N	N	N
weighted QU (worst case)	N	lg N	lg N	lg N

• 為什麼是 lg N 呢
  • 因為每次 union 後的 size 都會至少是小數的 2 倍大
  • 以 1, 2, 4, 8, 16, …成長
  • 所以 union 的次數一定會小於 lg N

CH2 演算法分析

• Big-

  ${\rm O}$ 代表演算法時間函式的上限(Upper bound)
  • 在最壞的狀況下，演算法的執行時間不會超過Big-Ο

• $\Omega$ 代表演算法時間函式的下限(Lower bound)
  • 在最好的狀況下，演算法的執行時間不會比Omega快

CH3 未知矩陣大小問題

Link-list

• 在最糟的情況下，執行時間為 constant
• 需要花很多空間來存 link

Resizing Arrays

• 每次執行，執行時間為 constant
• 不需要花太多空間

---

• 一次增加矩陣一格

  • 沒效率
  • $N+(2+4+6+8...+2(N–1))\to N^2$

• 一次增加原本矩陣的一半

  • 比較有效率
  • $N+(2+4+8+...+N)\to 3N$

• 一次減少四分之一

  • 會比一次減少二分之一還要有效率

CH4 sort

Selection sort 選擇排序法

• 流程

  1. 從 未排序 的數列中找到最小的元素
  2. 將此元素取出並加入到 已排序 數列最後
  3. 重複以上動作直到未排序數列全部處理完成

public static void sort(Comparable[] a) {

    int N = a.length;
    for (int i = 0; i < N; i++) {
        
        int min = i;
        
        for (int j = i+1; j < N; j++)
            if (less(a[j], a[min]))
                 min = j;
        
        exch(a, i, min);
    }
}

• 所花時間
  • compares：
    $(N–1)+(N–2)+...+1+0\to \frac{1}{2}{N}^2$
    • 隨著 i 漸漸往右，要比較的數字越來越少
  • exchange：
    $N$
    • 總交換數只要 N 個就可以了

Insertion sort 插入排序法

• 流程

  1. 從 未排序 數列取出一元素
  2. 由後往前和 已排序 數列比較
  3. 遇到 不大於自己 的元素並插入此元素之後
  4. 若都沒有則插入在最前面。
  5. 重複以上動作直到未排序數列全部處理完成。

public static void sort(Comparable[] a) {
    
    int N = a.length;
    
    for (int i = 0; i < N; i++)
        for (int j = i; j > 0; j--)
            if (less(a[j], a[j-1]))
                exch(a, j, j-1);
            else break;
}

• 所花時間
  • 最好情況
    • 如果數列已經是排好的
    • ex："1, 2, 3, 4, 5, 6"
    • compares：
      $N-1$
    • exchange：
      $0$
  • 最壞情況
    • 如果數列剛好是反過來排好的
    • ex："6, 5, 4, 3, 2, 1"
    • compares：
      $\frac{1}{2}{N}^2$
    • exchange：
      $\frac{1}{2}{N}^2$
  • 平均情況
    • compares：
      $\frac{1}{4}{N}^2$
    • exchange：
      $\frac{1}{4}{N}^2$

Shellsort

• 針對 Insertion sort 改良以下兩個方法

  • Insertion Sort 在對幾乎已經排好序的資料操作時，效率高
  • 但 Insertion Sort 一般來說是低效率的，因為每次只能將資料移動一位

---

• 流程
  1. 將整個陣列依照預先指定的間隔長度 d
  2. 交錯分割成數個小陣列
  3. 以插入排序的方式將這些小陣列個別排序
  4. 逐漸縮小間隔長度 d ，直到 d 等於 1
  5. 一般用 3x + 1 的方法

CH5 Merge sort 合併排序法

Top-Down Merge sort

• 使用 divide and conquer 分而治之的方法
• 使用遞迴的方法

---

• 流程

  1. 將陣列分割直到只有一個元素 -> 遞迴
  2. 開始兩兩合併，每次合併同時進行排序，合併出排序過的陣列
  3. 重複2的動作直接全部合併完成

merge 方法

private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {

    for (int k = lo; k <= hi; k++)   // 先 copy 到 aux 矩陣去
        aux[k] = a[k];

    int i = lo, j = mid+1;
    
    for (int k = lo; k <= hi; k++) {
        if (i > mid)                    a[k] = aux[j++];
        else if (j > hi)                a[k] = aux[i++];
        else if (less(aux[j], aux[i]))  a[k] = aux[j++];
        else                            a[k] = aux[i++];
    }
}

sort 方法

private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
    
    if (hi <= lo) 
        return;
    
    int mid = lo + (hi - lo) / 2;
    
    sort(a, aux, lo, mid);
    sort(a, aux, mid+1, hi);
    merge(a, aux, lo, mid, hi);         // 這邊遞迴
}

• 所花時間
  • compares：
    $NlogN$
  • proof：
    • $D(N)\le D(\lfloor N/2\rfloor )+D(\lceil N/2\rceil )+N$
      左半邊 + 右半邊 + merge
    • $D(N)=2D(N/2)+N$
    • 樹高為 lg N

• 特別注意
  • 只要演算法看起來是下面這個形式
  • 它一定會花
    $NlogN$

Buttion-Up Merge sort

• 比 Top-Down Merge sort 慢了一點

• 時間複雜度 N lg N

  • proof：

$D(N)=2D(\frac{N}{2})+N$

$\frac{D(N)}{N}=\frac{2D(\frac{N}{2})}{N}+1$

$\frac{D(N)}{N}=\frac{D(\frac{N}{2})}{\frac{N}{2}}+1$

$\frac{D(N)}{N}=\frac{D(\frac{N}{4})}{\frac{N}{4}}+1+1$

$\frac{D(N)}{N}=\frac{D(\frac{N}{8})}{\frac{N}{8}}+1+1+1$

$...$

$\frac{D(N)}{N}=\frac{D(\frac{N}{N})}{\frac{N}{N}}+1+1+...+1$

$\frac{D(N)}{N}=lgN$

sort 方法

public static void sort(Comparable[] a) {
    
    int N = a.length;
    
    Comparable[] aux = new Comparable[N];
    for (int sz = 1; sz < N; sz = sz+sz)
        for (int lo = 0; lo < N-sz; lo += sz+sz)
            merge(a, aux, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));
}

• 兩個 Merge sort 的比較

Timsort

• 結合了 merge sort 和插入排序 insertion sort 而得出的排序算法
• 為了優化在排序時有時已經排好的問題
• 以一個區塊進行排序

---

• 流程
  1. 找到各區塊
     $\to$ 以一個排好的數列為一區塊
  2. 以 merge sort 合併各個 區塊

stability 穩定性

• 如果在一個待排序的序列中，存在2個相等的數
• 在排序後這2個數的相對位置保持不變
• 那麼該排序演算法是穩定的
• 否則是不穩定的

ex：(A, A*, C, D, E)

$\to$(20, 20, 10, 50, 30)

stability

$\to$ (C, A, A*, E, D)
unstability

$\to$ (C, A*, A, E, D)

• 另一種看法
• 看有沒有長距離搬移
• 有的話就有可能是 unstability

Sleep sort

• 根據 thread 的 sleep
• 數字越小
  $\to$ 睡得越早，越早起來

CH6 Quick sort 快速排序法

quick sort

• 排序演算法的一種
• 使用Divide and Conquer的演算法來實作
• 可以使用 in-place 來實作，但不合成本

---

• 流程

  1. 數列中選擇一元素作為基準點(pivot)
  2. 小於此元素的移至基準的左邊，大於此元素的移至右邊，相等的任意放
  3. 基準點左邊和右邊視為兩個數列，並重複做以上動作直到數列剩下一個或零個元素。

• 所花時間

  • 最好情況

    • 當選中的 pivot 都是當下的中位數時
    • compares：
      $NlogN$

  • 最壞情況

    • 當數列已經是排好的了
    • compares：
      $\frac{1}{2}{N}^2$
    • proof：
    • $(N-1)+(N-2)+...+2+1\to \frac{1}{2}{N}^2$
      
      

  • 平均情況

    • $1.39NlogN$
    • proof：

表示本次 pivot 所需比較次數

$(n+1)$
與每種分割結果所需比較次數的期望和

$C_n=(n+1)+(\frac{C_0+C_{n-1}}{n})+(\frac{C_1+C_{n-2}}{n})+...+(\frac{C_{n-1}+C_0}{n})$

通乘以 n 得

$n{C}_n=n(n+1)+2(C_0+C_1+C_2+...+C_{n-1})$

$\to$ 式1

把 n 換成 n - 1 得

$(n-1)C_{n-1}=(n-1)(n-1+1)+2(C_0+C_1+C_2+...+C_{n-2})$

$\to$ 式2

把 式1 - 式2 得

$n{C}_n-(n-1)C_{n-1}=2n+2C_{n-1}$

移位後，同除以

$n(n+1)$ 得

$\frac{C_n}{n+1}$

$=\frac{C_{n-1}}{n}+\frac{2}{n+1}$

$=\frac{C_{n-2}}{n-1}+\frac{2}{n}+\frac{2}{n+1}$

$=\frac{2}{3}+\frac{2}{4}+\frac{2}{5}+...+\frac{2}{n+1}$

用積分化減得

$C_n=2(n+1)(\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+...+\frac{1}{n+1})$

$C_n=2(n+1){\int }_3^{n+1}\frac{1}{x}dx$

$C_n=2(n+1)lnN\cong 1.39NlgN$

3 ways quick sort

• 用來解決 quick sort 遇到一樣的數字時，會再 compare 一次
• 原本 quick sort 只會分成兩等分：大於 pivot 或小於 pivot
• 3 ways 則分成三等分：大於 pivot、等於 pivot、小於 pivot

---

• 流程

  1. (a[i] < v)：交換 a[lt] 和 a[i]、增加 lt 和 i
  2. (a[i] > v)：交換 a[gt] 和 a[i]、減少 gt
  3. (a[i] == v)：增加 i

總整理

	inplace	stable	最好情況	平均情況	最壞情況	優點
selection	✔		$\frac{1}{2}{N}^2$	$\frac{1}{2}{N}^2$	$\frac{1}{2}{N}^2$	只交換 N 次
insertion	✔	✔	N	$\frac{1}{4}{N}^2$	$\frac{1}{2}{N}^2$	如果 N 特別小的話 效率高，會接近 constant
shell	✔		$NlogN$	?	?
merge		✔	$\frac{1}{2}NlogN$	$NlogN$	$NlogN$	穩定保證 $NlogN$
timsort		✔	N	$NlogN$	$NlogN$	改良 mergesort 優化已經排序的數列
quick	✔		$NlogN$	$1.39NlogN$	$\frac{1}{2}{N}^2$	最快的排序法
3-way quick	✔		N	$NlogN$	$NlogN$	優化 quicksort 遇到相同數字的問題
heap	✔		N	$2NlogN$	$2NlogN$	保證 $NlogN$

Heap Sort