[Data Structure & 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) (嚴格一點說，是 Ω(1))，因為如果目標值在陣列的第一個位置，那只需要一次比較就可以找到目標值。
而 linearSearch 的 Big Θ，以平均來說，落點會是 n/2，但因為會忽略常數，所以 Big Θ 也是 O(n) (嚴格一點說，是 Θ(n))。

常見的時間複雜度分類

資訊

Log 小筆記

log 是什麼？
- log_b(n) 就是「底 b 要幾次方才能得到 n？」
- 例：log₂(8) = 3 → 因為 2³ = 8
幾個常用規則
- log(a * b) = log a + log b
- log(a / b) = log a - log b
- log(a^k) = k * log a
換底公式
- log_b(n) = log_k(n) / log_k(b)
- Big-O 分析通常不用管底數
直覺理解
- log 告訴你「要把 n 變成 1 需要幾次折半」
- 增長非常慢，比線性 n 慢很多，所以演算法裡 log 的複雜度通常很快

O(1)：常數時間複雜度，無論輸入的規模多大，執行時間都是固定的。
O(n)：線性時間複雜度，執行時間與輸入的規模成正比。
O(n^2)：平方時間複雜度，當輸入規模增長，執行時間呈平方成長。
舉例來說，假設一個演算法的時間複雜度是 O(n^2)，當 n = 3 時，執行時間可能是 3^2 = 9 單位時間。當 n = 4 時，執行時間可能是 4^2 = 16 單位時間。
O(log n)：對數時間複雜度，當輸入規模增長，執行時間呈對數成長。
舉例來說，假設一個演算法的時間複雜度是 O(log n)，當 n = 8 時，執行時間可能是 3 個單位時間。當 n = 16 時，執行時間可能是 4 個單位時間。雖然 n 增加了一倍，但執行時間只增加了一個單位時間。
O(n log n)：線性對數時間複雜度，當輸入規模增長，執行時間以 n 乘以 log n 的速率增長。
舉例來說，假設一個演算法的時間複雜度是 O(n log n)，當 n = 8 時，執行時間可能是 ``8 * log₂(8) = 24 單位時間。當 n = 16 時，執行時間可能是 16 * log₂(16) = 64 單位時間。儘管 n 增加了一倍，但執行時間增長了更多，以 n 乘以 log n 的速率增長。
O(2^n)：指數時間複雜度，當輸入規模增長，執行時間呈指數成長。
舉例來說，當 n = 3 時，執行時間可能是 2^3 = 8 單位時間。當 n = 4 時，執行時間可能是 2^4 = 16 單位時間。
O(n!)：階乘時間複雜度，隨著輸入規模 n 的增加，執行時間以階乘方式增長。
舉例來說，當 n = 3 時，執行時間可能是 3! = 6 單位時間。當 n = 4 時，執行時間可能是 4! = 24 單位時間。

提示

時間複雜度速率排序

Complexity	Speed
O(1)	很快
O(log n)	快
O(n)	中
O(n log n)	慢
O(n^2)	很慢
O(2^n)	非常慢
O(n!)	超級慢

資料結構與演算法概論​

資料結構 (Data Structure)​

資料結構的目標​

資料結構的種類​

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

演算法 (Algorithm)​

演算法具備五大特性​

時間/空間複雜度概論​

時間複雜度​

空間複雜度​

Big O notation​

常見的時間複雜度分類​