---
###### tags: `Program` `Algorithm`
---
Algorithm 演算法
===

\# 這裡出現的 $log$，皆為 $log_2$。

:::warning
**Program = Data Structure + Algorithm**

> **Algorithm**
> 是一種用於處理某件特定事情的方法

> **[Data Structure](https://)**
> 是資料的組織、管理和處理格式，為了能高效存取和修改資料

**資料結構和演算法不分家，有了資料結構，演算法才可以盡情發揮。**
:::

## Information
### 什麼是演算法(Algorithm)?
要處理一件事，我們會希望可以用一個快速有效的方式處理，就如同大家生活中，也會有一些事有固定步驟，而這步驟可能就是我們經過一些經驗，所得知較為有效的方式:

    洗衣服:

    1. 收集衣服
    2. 將衣服放入洗衣機
    3. 倒入洗衣精
    4. 按下啟動鍵，洗衣機開始運轉
    5. 等待運作完成
    6. 運作完成，將衣服取出
    

:::warning
在數學領域中，有一些演算法，使計算變得更快速，以下有個例子:

**==計算 1 + 2 + 3 + 4 + 5 + ... + 10000 = ?==**

方法一:

1 + 2 = 3
3 + 3 = 6
6 + 4 = 10
10 + 5 = 15
......
49995000 + 10000 = 50005000 #

方法二:

1 + 10000 = 10001
2 + 9999 = 10001
3 + 9998 = 10001
4 + 9997 = 10001
......

(1 + 10000) * 10000 / 2 = 50005000 #

> 方法二是高斯演算法，運用等差數列求和的方法，方法二比方法一運算速度更快。
:::

:::info
**而電腦領域中也有演算法，是由執行時間與執行空間來決定哪一個方式較為妥當，
也可以稱為 ==時間複雜度(Time Complexity)== 與 ==空間複雜度(Space Complexity)==，
當時間複雜度和空間複雜度用的越少，程式就越好。**
:::

### 時間複雜度(Time Complexity)
> 由於受執行環境和輸入規模的影響，程式碼的絕對執行時間是無法預估的。
> 但我們可以預估程式碼的基礎操作執行次數。

#### 基本操作執行次數
設定 $T(n)$ 為程式基本操作執行次數的函數，也可以認為是程式的相對執行時間函數，$n$ 為輸入規模。

**例一:**

void eat1(int n){
    for(int i = 0; i < n; i++){
        System.out.println("等待1分鐘");
        System.out.println("等待1分鐘");
        System.out.println("吃1cm麵包");
    }
}

> $T(n) = 3n$，執行次數是**線性**的。

**例二:**

void eat2(int n){
    for(int i = n; i > 1; i /= 2){
        System.out.println("等待1分鐘");
        System.out.println("等待1分鐘");
        System.out.println("等待1分鐘");
        System.out.println("等待1分鐘");
        System.out.println("吃一半麵包");
    }
}

> $T(n) = 5log^n$，執行次數是用**對數**計算的。

**例三:**

void eat3(int n){
    System.out.println("等待1分鐘");
    System.out.println("吃1隻雞腿");
}

> $T(n) = 2$，執行次數是**常數**。

**例四:**

void eat4(int n){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < i; j++){
            System.out.println("等待1分鐘");
        }
        System.out.println("吃1cm麵包");
    }
}

> $T(n) = 0.5n^2 + 0.5n$，執行次數是用**多項式**計算的。

#### 漸進時間複雜度(Asymptotic time complexity)
:::info
哪一個演算法執行時間更長一點，要看 $n$ 的值。
$f(n)$ 表示為當 $n$ 趨近於無限大時，可將 $T(n)$ 看做與 $O(f(n))$ 相同，
$T(n) = O(f(n))$，$O(f(n))$ 為演算法的漸進時間複雜度，用 $big O$ 表示。
<br/>

**==Asymptotic Notation (O)==**
**\# [Big "oh"] (Upper bound 上限)**

**$f(n) = O(g(n))$
iff there exist positive constants $c$ and $n_0$ such that $f(n) <= cg(n)$ for all $n$, $n >= n_0$** .
:::

> 時間複雜度是把程式的相對執行時間函數 $T(n)$ 簡化為一個數量級。

* 如果執行時間是常數量級，則用常數 $1$ 表示。
* 只保留時間函數中的最高階項。
* 如果最高階項存在，則省去最高階項前面的係數。

**例一:**
> 最高階項為 $3n$，省去係數 $3$ : $T(n) = 3n$， $T(n) = O(n)$。


**例二:**
> 最高階項為 $5log^n$，省去係數 $5$ : $T(n) = 5log^n$， $T(n) = O(log^n)$。


**例三:**
> 只有常數量級 : $T(n) = 2$， $T(n) = O(1)$。


**例四:**
> 最高階項為 $0.5n^2$，省去係數 $0.5$ : $T(n) = 0.5n^2 + 0.5n$， $T(n) = O(n^2)$。


:::success
#### Basic Principle 基本原理

* **$O(1)$ : constant**
* **$O(log^n)$ : logarithmic**
* **$O(n)$ : linear**
* **$O(nlog^n)$ : log linear**
* **$O(n^2)$ : quadratic**
* **$O(n^3)$ : cubic**
* **$O(2^n)$ : exponential**
* **$O((\frac{n}{2})^\frac{n}{2})$**
* **$O(n!)$ : factorial**
* **$O(n^n)$**
<br/>
:::

### 空間複雜度(Space Complexity)
在執行一段程式時，我們不僅要執行各種運算指令，**同時也會根據需要，儲存一些臨時的中間資料**，以便後續指令可以更方便的繼續執行。

#### 中間資料
:::warning
==**如下圖列出的 n 個整數，其中有兩個整數是重複，要求找出這兩個重複的整數。**==


==**方法一:**==

> 第 1 步，遍訪整數 3，前面沒有數字，所以無需回顧比較。

> 第 2 步，遍訪整數 1，回顧前面的數字 3，沒有發現重複數字。

> 第 3 步，遍訪整數 2，回顧前面的數字 3、1，沒有發現重複數字。
> ...

> 後面步驟類似，一直遍訪到最後的整數 2，發現和前面的整數 2 重複。

> **雙重迴圈**，雖然這個方法可以的得到最終結果，但他的時間複雜度為 $O(n^2)$，顯然不是一個好的演算法。

==**方法二:**==


> 假如已經遍訪了數列的前 7 個整數，那麼字典裡儲存的資料如上。


> 接下來，當遍訪到最後一個整數 2 時，從「字典」中可以輕鬆找到 2 曾經出現過。

> **利用中間資料**，每遍訪一個整數，就把該整數儲存起來，就像放到字典中一樣。
> 當遍訪下一個整數時，不必再慢慢向前回溯比較，而直接去「字典」中尋找，看有沒有相對應的整數。
> 由於讀寫「字典」本身的時間複雜度是 $O(1)$，所以整個演算法的時間複雜度是 $O(n)$，和方法一的雙重迴圈相比，執行效率大大提高。

> 而這個所謂的「字典」，是一種特殊的資料結構，稱作**雜湊表**。
> 這個資料結構需要開闢一定的記憶體空間來儲存有用的資料資訊。
> 「字典」上側的 Key 代表整數的值，「字典」下側的 Value 代表該整數出現的次數(也可以只記錄 Key )。
:::

但是，記憶體空間有限，在時間複雜度相同的情況下，演算法占用記憶體空間自然是越小越好。
空間複雜度是對一個演算法在執行過程中臨時占用儲存空間大小的量度，同樣使用 `big O`。

程式佔用空間大小的計算公式記作 $S(n) = O(f(n))$，其中 $n$ 為問題的規模，$f(n)$ 為演算法所占儲存空間的函數。

#### 空間複雜度的計算
:::info
**常數空間**

void fun1(int n){
    int var = 3;
    ...
}

> 當演算法的儲存空間大小固定，和輸入規模沒有直接的關係時，空間複雜度記作 $O(1)$。

**線性空間**

void fun2(int n){
    int[] array = new int[n];
    ...
}

> 當演算法分配的空間是一個線性的集合(如陣列)，並且集合大小和輸入規模 n 成正比時，空間複雜度記作 $O(n)$。

**二為空間**

void fun3(int n){
    int[][] matrix = new int[n][n];
    ...
}

> 當演算法分配的空間是一個二維陣列集合，且集合的長度和寬度都與輸入規模 n 成正比時，空間複雜度記作 $O(n^2)$。

**遞迴空間**

void fun4(int n){
    if(n <= 1){
        return ;
    }
    fun4(n - 1);
    ...
}

> 遞迴是一個特殊的空間，雖然遞迴程式碼中並沒有以顯式來宣告變數或集合，但是電腦在執行程式時，會專門分配一塊記憶體，用來儲存「方法呼叫堆疊」。
> 如果遞迴的深度是 $n$，那麼空間複雜度就是 $O(n)$。

> 「方法呼叫堆疊」包括**進堆疊**和**出堆疊**兩個行為。
> 當進入一個新方法時，執行進堆疊，把呼叫的方法和參數資訊都壓進堆疊中。
> 當方法返回時，執行出堆疊，把呼叫的方法和參數資訊從堆疊中彈出。

> 最終，「方法呼叫堆疊」的全部元素會一一出堆疊。
> 執行遞迴操作所需要的記憶體空間和遞迴的深度成正比。
:::

### 時間與空間的取捨
人們之所以花大力氣去評估演算法的時間複雜度和空間複雜度，根本原因是電腦的運算速度和空間資源是有限的。

但是，很多時候我們不得不在時間複雜度和空間複雜度之間進行取捨。

> 有兩種，一種是***犧牲時間來換取空間***，另一種是***犧牲空間來換取時間***。

==**在絕大多數時候，時間複雜度更為重要一些，我們寧可多分配一些記憶體空間，也要提升程式的執行速度。**==

## Sorting Algorithm
### infomation
:::warning
==**最主流的排序演算法**==

**時間複雜度為 $O(n^2)$ 的排序演算法**
* 泡沫排序
* 選擇排序
* 插入排序
* 希爾排序 (這個比較特殊，效能略優於 $O(n^2)$，但又比不上 $O(nlog^n)$，故歸於此類)

**時間複雜度為 $O(nlog^n)$ 的排序演算法**
* 快速排序
* 歸併排序
* 堆積排序

**時間複雜度為 線性 的排序演算法**
* 計數排序
* 桶排序
* 基數排序
:::

排序驗算法可以分為 ==**穩定排序**== 和 ==**不穩定排序**==


:::info
### **Bubble Sort(泡沫排序)**

Usage:
: 用於對一筆資料排順序，是**穩定排序**。

**Time Complexity: $O(n^2)$**

**Space Complexity: $O(1)$**

**Code**

==**泡沫排序 1.0:**==

基礎泡沫排序。

public static void sort(int array[]){
    for(int i = 0; i < array.length - 1; i++){
        for(int j = 0; j < array.length - i - 1; j++){
            int temp = 0;
            if(array[j] > array[j + 1]){
                temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            } //swap
        }
    }
}

public static void main(String[] args){
    int[] array = new int[]{5, 8, 6, 3, 9, 2, 1, 7};
    sort(array);
    System.out.println(Arrays.toString(array));
}

==**泡沫排序 2.0:**==

在某些要排序的資料可能不用全部跑完 ***$n$次*** 就排好了，因此這個寫法可避免。

public static void sort(int array[]){
    for(int i = 0; i < array.length - 1; i++){
        
        //有序標記，每一輪的初始值都是true
        boolean isSorted = true;
        for(int j = 0; j < array.length - i - 1; j++){
            int temp = 0;
            if(array[j] > array[j + 1]){
                temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
                
                //因為有元素進行交換，所以不是有序的，標記變為false
                isSorted = false;
            } //swap
        }
        if(isSorted){
            break;
        }
    }
}

public static void main(String[] args){
    int[] array = new int[]{5, 8, 6, 3, 9, 2, 1, 7};
    sort(array);
    System.out.println(Arrays.toString(array));
}

==**泡沫排序 3.0:**==

在某寫資料中，有的後面的順序是排好的，這個方法是避免重複排序後面已經排序好的地方。

public static void sort(int array[]){
    //紀錄最後一次交換的位置
    int lastExchangeIndex = 0;
    //無序數列的邊界，每次比較只需要比到這裡為止
    int sortBorder = array.length - 1;
    for(int i = 0; i < array.length - 1; i++){
        
        //有序標記，每一輪的初始值都是true
        boolean isSorted = true;
        for(int j = 0; j < sortBorder; j++){
            int temp = 0;
            if(array[j] > array[j + 1]){
                temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
                
                //因為有元素進行交換，所以不是有序的，標記變為false
                isSorted = false;
                //更新為最後一次交換元素的位置
                lastExchangeIndex = j;
            } //swap
        }
        sortBorder = lastExchangeIndex;
        if(isSorted){
            break;
        }
    }
}

public static void main(String[] args){
    int[] array = new int[]{5, 8, 6, 3, 9, 2, 1, 7};
    sort(array);
    System.out.println(Arrays.toString(array));
}

:::

<br/>

:::info
### Cocktail Sort(雞尾酒排序)

Usage:
: 雙向的泡沫排序法。

**Time Complexity: $O(n^2)$**

**Space Complexity: $O(1)$**

**Code**

public static void sort(int[] array){
    int temp = 0;
    for(int i = 0; i < array.length/2; i++){
        //有序標記，每一輪的初始值都是true
        boolean isSorted = true;
        
        //奇數輪，從左向右比較和交換
        for(int j = i; j < array.length - i - 1; j++){
            if(array[j] > array[j + 1]){
                temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
                
                //有元素交換，所以不是有序的，標記變為false
                isSorted = false;
            } //swap
            if(isSorted){
                break;
            }
        }
        
        //在偶數輪之前，將 isSorted 重新標記為 ture
        isSorted = true;
        //偶數輪，從右向左比較和交換
        for(int j = array.length - i - 1; j > i; j--){
            if(array[j] > array[j - 1]){
                temp = array[j];
                array[j] = array[j - 1];
                array[j - 1] = temp;
                
                //有元素交換，所以不是有序的，標記變為false
                isSorted = false;
            } //swap
            if(isSorted){
                break;
            }
        }
    }
}

public static void main(String[] args){
    int[] array = new int[]{5, 8, 6, 3, 9, 2, 1, 7};
    sort(array);
    System.out.println(Arrays.toString(array));
}

:::

<br/>

:::info
### Quick Sort(快速排序)

Usage:
: 用於排序，在每一輪挑選一個基準元素

**Time Complexity: $O(nlog^n)$**
最壞情況下的時間複雜度是 $O(n^2)$

**Space Complexity: $O(1)$**

**Code**
:::

<br/>

### Heap Sort(堆積排序)

Usage:
: how to use

**Time Complexity:**

**Space Complexity:**

**Code**

<br/>

## Monotonic Stack

Usage:
: how to use

**Time Complexity:**

**Space Complexity:**

**Code**

<br/>

## Monotonic Stack

Usage:
: how to use

**Time Complexity:**

**Space Complexity:**

**Code**

<br/><br/>

> [time=Thu, Jan 19, 2023 8:24 PM]

> [name=HsingyuChen]