[Algorithm] 資料結構 & 演算法概論

對 computer science 來說，資料結構與演算法基本是不可或缺的基礎知識。
概念上來說，程式語言的本質就是資料結構與演算法的組合。
資料結構代表資料處理的過程中，分析、組織資料的方法語邏輯。
演算法則是設計一連串的指令、動作讓電腦執行，在「有限的」步驟下完成、解決問題。

資料結構 (Data Structure)

資料結構的目標

空間佔用盡量少，以節省記憶體空間 → 空間複雜度
資料的操作可以快速處理 CRUD (Create, Read, Update, Delete)
提供簡潔的資料表示和邏輯資訊，以便演算法提高執行效能 → 時間複雜度

資料結構的種類

依邏輯結構分類

線性結構 (Linear Structure)：
- 陣列 (Array)
- 鏈結串列 (Linked List)
- 堆疊 (Stack)
- 佇列 (Queue)
非線性結構 (Non-linear Structure)：
- 樹 (Tree)
- 圖 (Graph)
- 雜湊表 (Hash Table)

依物理結構分類

連續空間 (Contiguous Storage)
- 一般只有陣列 (Array)
非連續空間 (Non-contiguous Storage)
- 除陣列外多數的資料結構

資料的內容型態 vs 資料結構

電腦中的資料，包含文字、圖片、影像等各種形式，但都是由各種資料型態所組成。
而資料型態指的是如整數類型 (byte, short, long, int)、浮點數類型 (float, double)、字元類型 (char)、布林類型 (boolean) 等等，一般會更親切地稱呼為「型別」(type)。
而資料型態表示的是資料的內容型態，資料結構則是表示資料的組織方式。
以 int [] arr = new int[5]; 為例，int 是資料型態，int[] 是資料結構 (陣列)。

演算法 (Algorithm)

演算法具備五大特性

輸入 (Input)：演算法有零個或多個輸入。
輸出 (Output)：演算法有一個或多個輸出。
有限性 (Finiteness)：演算法必須在有限的步驟內結束。
明確性 (Definiteness)：演算法的每一步驟必須是明確的，不能含糊不清。
可行性/有效性 (Effectiveness)：演算法的每一步驟必須是可行的，能夠在有限的時間內完成。

時間/空間複雜度概論

演算法的好壞，通常會以時間複雜度 (Time Complexity) 和空間複雜度 (Space Complexity) 來評估，都會以 Big O 符號來表示。
時間複雜度表示演算法執行所需的時間，空間複雜度表示演算法執行所需的記憶體空間。
其實通常講複雜度都會先講時間複雜度，因為時間複雜度通常是影響程式效能的主要因素。空間複雜度雖然也重要，但一般要資料量非常大，或是記憶體非常有限的情況下，才會特別注意空間複雜度。
往細處說，複雜度其實是指演算法中用了多少基本運算 (Basic Operation)：
- 時間複雜度：基本運算是指演算法中最耗時的操作，例如比較、賦值、算術運算等。
- 空間複雜度：基本運算是指演算法中使用的額外記憶體空間，例如變數、陣列、物件等。
複雜度，或者說演算法，通常以 $f(n)$ 來表示， $n$ 是輸入的規模 (size)， $f(n)$ 是演算法執行所需的基本運算次數。

時間複雜度

以下述範例來說明時間複雜度：

範例一：印出名字。因為不論名字長度如何，印出名字的動作都是固定的，所以時間複雜度是 $O(1)$ 。

void printName (String name) {
    System.out.println(name); // O(1)
}

範例二：用迴圈累加 1-10 的數字總和。因為迴圈會根據輸入 n 的大小執行 n 次，所以時間複雜度是 $O(n)$ 。

int sum (int n) {
    int total = 0;
    for (int i = 1; i <= n; i++) { // O(n)
        total += i;
    }
    return total;
}

範例三：用兩層迴圈印出 1-10 的乘法表。因為外層迴圈會根據輸入 n 的大小執行 n 次，內層迴圈也會根據輸入 n 的大小執行 n 次，所以時間複雜度是 $O(n^2)$ 。

void multiplicationTable (int n) {
    for (int i = 1; i <= n; i++) { // O(n)
        for (int j = 1; j <= n; j++) { // O(n)
            System.out.print(i * j + " ");
        }
        System.out.println();
    }
}

空間複雜度

以下述範例來說明空間複雜度：

範例一：用迴圈印出 1-10 的數字。因為只需要一個記憶體空間來存放變數 i，所以空間複雜度是 $O(1)$ 。

void printNumbers() {
    for (int i = 1; i <= 10; i++) { // O(1)
        System.out.println(i);
    }
}

範例二：用陣列存放 1-10 的數字。因為需要一個陣列來存放 n 個數字，所以空間複雜度是 $O(n)$ 。

void storeNumbers(int n) {
    int[] numbers = new int[n]; // O(n)
    for (int i = 0; i < n; i++) {
        numbers[i] = i + 1;
    }
}

Big O notation

嚴格來說，Big O notation 除了基本的 Big O，還有 Big Ω (Big Omega) 和 Big Θ (Big Theta)，分別表示演算法的最佳時間複雜度和平均時間複雜度。
但在實務上，通常只會用 Big O 來表示演算法的時間複雜度，因為通常大家最關心的是演算法在最壞情況下的表現。

Big O 表示的是 $f(n)$ 的漸近上界 (asymptotic upper bound)，也就是當 $n$ 趨近無限大時， $f(n)$ 的增長速率不會超過某個函數 $g(n)$ 的增長速率。白話來說，Big O 是用來描述演算法在最壞情況下的時間複雜度。
Big Ω 表示的是 $f(n)$ 的漸近下界 (asymptotic lower bound)，也就是當 $n$ 趨近無限大時， $f(n)$ 的增長速率不會低於某個函數 $g(n)$ 的增長速率。白話來說，Big Ω 可以說是用來描述演算法在最佳情況下的時間複雜度。但嚴格來講是「趨近於」最佳情況。
Big Θ 表示的是 $f(n)$ 的漸近緊界 (asymptotic tight bound)，也就是當 $n$ 趨近無限大時， $f(n)$ 的增長速率與某個函數 $g(n)$ 的增長速率相同。其實 Big Θ 可以看作是 Big O 和 Big Ω 的結合。

在一般數學下，也就是如果只單看 $f(n)$ ，那 Big O、Big Ω、Big Θ 其實不會有差別。
但如果是在探討演算法的其他情況時，Big O 依舊可以直接從 $f(n)$ 推導出來，但 Big Ω 和 Big Θ 就不一定了。
舉例來說，以下是個陣列跟一個查找演算法：

int[] arr = {1, 2, 3, 4, 5};
boolean linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) {
            return true;
        }
    }
    return false;
}

linearSearch 的演算法表示為 $f(n) = n$ ，這種情況下，可以說單看 $f(n)$ 的 Big O、Big Ω、Big Θ 都是 $O(n)$ 。
但其實，linearSearch 的 Big Ω 應該是 $O(1)$ (嚴格一點說，是 $\Omega(1)$ )，因為如果目標值在陣列的第一個位置，那只需要一次比較就可以找到目標值。
而 linearSearch 的 Big Θ，以平均來說，落點會是 $n/2$ ，但因為會忽略常數，所以 Big Θ 也是 $O(n)$ (嚴格一點說，是 $\Theta(n)$ )。

常見的時間複雜度分類

在看時間複雜度的分類之前，咱們先來複習高中數學~~~
什麼是 $\log$ ？

$\log$ 是對數的意思，基本公式是 $\log_a(N) = b$ ，其中 $a$ 是底數 (base)， $N$ 是真數 (argument)， $b$ 是對數的值。
但我們不是專門學數學的，也沒人會對我們考試，我們只要記得 $a$ 的 $b$ 次方等於 $N$ 就好了，也就是 $a^b = N$ 。
在我們不給定底數 ( $a$ ) 的情況下，通常會默認為 10，也就是 $\log_{10}(N)$ ，但電腦的世界是二進位的宇宙，所以默認的底數是 2，也就是 $\log_2(N)$ 。

等等下面會看到的 $\log$ 有這些：

$\log n$ ：表示這個演算法的花費時間會是輸入資料尺寸 $n$ 的對數級別，簡單一點想像，就是「資料每次都能砍半處理」，所以它的增長速度非常慢，效能極佳！
$n \log n$ ：就是前者多乘以了 $n$ ，所以理所當然時間花費會多一點點。

然後加一個數學的比較： $2 ^ n$ 跟 $\log n$ 哪個大？
我們得先知道的是，對數算出來的值，以 $\log_a(n) = b$ 為例， $b$ 是一定會比 $n$ 小的。
但如果是 $2^n$ 的話，結果一定是比 $n$ 大的。
所以 $2^n$ 比 $\log n$ 大很多~

$O(1)$ ：常數時間複雜度，無論輸入的規模多大，執行時間都是固定的。
$O(\log n)$ ：對數時間複雜度，當輸入規模增長，執行時間呈對數成長。
$O(n)$ ：線性時間複雜度，執行時間與輸入的規模成正比。
$O(n \log n)$ ：線性對數時間複雜度，當輸入規模增長，執行時間以 $n$ 乘以 $\log n$ 的速率增長。
$O(n^2)$ ：平方時間複雜度，當輸入規模增長，執行時間呈平方成長。
$O(2^n)$ ：指數時間複雜度，當輸入規模增長，執行時間呈指數成長。
$O(n!)$ ：階乘時間複雜度，隨著輸入規模 $n$ 的增加，執行時間以階乘方式增長。