---
# System prepended metadata

title: "\U0001F4DD Chapter 1 資料結構與演算法"
tags: [資料結構]

---

# 📝 Chapter 1 資料結構與演算法
### 1-1 資料結構的定義
#### 重點說明
* 資料結構（Data Structure）是如何組織 *(資料彼此之間的關係與運算)* 、儲存資料，讓資料能被「高效地使用」 *(加速執行、減少記憶體空間)*
換句話說，它決定資料之間的關係如何存取、搜尋、插入、刪除 *(CRUD的方法)*

#### 主要概念
* 資料（Data）:未經過整理的原始文字、數字、符號、圖形，本身無意義
* 資訊（Information）：是把資料「整理、歸納、分析」之後產生的有意義結果
* 資料處理（Data Processing）：將資料轉換成資訊的過程

**例子**
```m    
銀行儲戶的交易資料明細 = Data
計算後的帳戶餘額 = Information
```

#### 資料特性：電腦如何看待資料
1. 基本資料型態：
    * 不能拆解的最基本型態，電腦底層知道如何儲存它們
    * 例如：C#的整數(int)、浮點數(float)、字元(char)...
2. 結構化資料型態：
    * 由多個基本資料組合而成，也就是「資料容器」的概念
    * 例如：字串(string)、陣列(array)、指標(pointer)、串列(list)、檔案(file)
    ```C#
    ● string 是由多個 char 組成的結構
    ● array 是一組相同型態的資料
    ● list 、 dictionary、 file 屬於更進階的結構
    ```
    * `int` 是原料，而`int[]`或`List<int>`是完整包裝完的資料結構。
3. 抽象資料型態（ADT）
    * 只定義資料能做什麼操作（行為），而不管它內部是怎麼實作的
    * 就是「資訊隱藏（Information Hiding）」
    * `stack` 是「LIFO（後進先出）」的行為，`Queue`是「FIFO（先進先出）」的行為
    * 以 `stack` 為例子：
        | 動作名稱 | 說明| 
        | -------- | -------- | 
        | Push()    | 把資料放進堆疊  |
        | Pop()    | 把最上面的資料取出 |
        | Peek()    | 查看最上面的資料但不取出  |
        * 使用者不需要知道裡面是用陣列還是鏈結串列實作
        * 他只要知道「可以 Push / Pop」即可

#### 討論題
👉 `Stack` 跟 `Queue` 很像，只是資料取得方向反過來，生活上有沒有甚麼例子有運用到?
👉 你每天收到很多訊息（Line、Email、通知），如果要快速找到某一個人的訊息，會怎麼整理？

---
### 1-2 演算法

#### 重點說明
演算法是解決問題的步驟或方法。
一個好的演算法應該具備：
1. 明確性（每一步都清楚）
2. 有限性（會在有限時間結束）
3. 輸入與輸出明確
4. 效率高（執行時間與資源消耗合理）
![image](https://hackmd.io/_uploads/Sks17Mskbx.png)

> 韋氏辭典定義：演算法是在有限步驟內解決數學問題的程式


#### 例子：「泡咖啡」的步驟就是一個演算法。
``` 
步驟明確（加水 → 加粉 → 攪拌）
有結果（得到咖啡）
若中間無限攪拌，就不算好演算法。
```
#### 討論題
👉 日常生活中有什麼事情可以被你定義成一個「演算法」？
👉 生活中有沒有經驗「照順序做事很慢，換一個方法就快很多」？

---
### 1-3 演算法效能分析
####  重點說明
* 目的是衡量演算法「快不快」、「省不省」。
* 通常用「時間複雜度」和「空間複雜度」來描述。

🕒 **時間複雜度（Time Complexity）**
用 Big O 表示法 來估算「最壞情況」下所需的運算次數，也就是程式運行的時間。

**常見等級：**
| 複雜度 | 定義 | 範例 | 備註 |
| -------- | -------- | -------- | -------- |
| O(1) | 執行時間固定，不隨資料量增減而變化 |  直接取值`array[0]` | 超快 | 
| O(log n) | 每次操作可將資料量減半，逐步逼近結果 |  二分搜尋 | 高效率搜尋 | 
| O(n) | 執行時間與資料量成正比 |  單一迴圈 `for` 遍歷陣列 | 隨資料線性成長 | 
| O(n²) | 執行時間與資料量平方成正比 |  雙重迴圈 `for` 巢狀迴圈 | 效能明顯下降 | 
| O(2ⁿ) | 執行時間呈指數增長 |  遞迴組合、列舉所有子集合 | 資料量稍大就爆炸，非常慢 | 


| 複雜度 | 定義 | 範例 | 備註 | 
| -------- | -------- | -------- | -------- |
| O(log₂ n)   | 每次操作能將資料量**減半**，逐步逼近結果 | 二分搜尋 | 典型的「對半找」策略，效率很高 |
| O(n³)  | 執行時間與資料量的立方成正比 | 三重巢狀迴圈，例如：矩陣三重迴圈運算  | 資料量稍大就會非常慢 |
| O(n log₂ n) | 執行時間與資料量 **線性*對半找*結合** | 高效率排序（如 Merge Sort、Quick Sort） | 常見高效排序演算法，比 O(n²) 好很多 |


![image](https://hackmd.io/_uploads/ByoTdMjk-x.png)

💡小提示：
* O(1) → 常數時間，像「直接拿抽屜裡第一件衣服」
* O(log n) → 對半找，像「翻電話簿找名字」
* O(n) → 遍歷，像「一個一個翻書找章節」
* O(n²) → 每個都比對，像「比對班上每個同學的座位」
* O(2ⁿ) → 全排列，像「試所有衣服搭配組合」
* O(log₂ n) → 找書櫃某本書，用「每次翻半本書」的方法，很快找到。
* O(n³) → 比對班上每個學生三個屬性，每個人都要對每個人操作，超慢。
* O(n log₂ n) → 整理衣櫃的方法：先把衣服分區（log n），再每區依次整理（n），效率比單純兩層迴圈高。

💾 **空間複雜度（Space Complexity）**
指演算法執行時需要多少額外記憶體。
又分成「固定空間記憶體」、「變動空間記憶體(參考型別)」。

#### 例子
```
搜尋一個電話號碼
逐一找（O(n)）
用二分搜尋（O(log n)）
```

#### 討論題
👉 如果資料量從 100 筆變成 1000 筆，演算法效能會怎麼變？

---
### 1-4 常見演算法介紹

#### 重點說明


**1. 遞迴法（Recursion）**
* 函式直接或間接呼叫自己（如：階乘、費波那契數列）

**2. 分治法（Divide and Conquer）**
* 把問題拆成小問題再組合答案（例：Merge Sort）
![image](https://hackmd.io/_uploads/S1B5qMi1Zl.png)

**3. 貪心法（Greed Method）**
* 每一步都選擇 當前看起來最好的選擇，希望最後得到整體最佳解
* 不一定總是正確，但在某些問題上效率很高

**4. 動態規劃法（Dynamic Programming, DP）**
* 把大問題拆成小問題，記錄小問題的結果，避免重複計算
* 最終組合小問題結果得到整體最佳解

**5. 疊代法（Iterative Method）**
* 「重複執行某個步驟直到達成條件」 的方法
* 例子：「牛頓疊代法」(Newton’s Iteration Method)
    ```C#
    double SqrtIterative(double n)
    {
        double x = n;          // 初始猜測
        double epsilon = 0.00001;  // 誤差允許範圍

        while (Math.Abs(x * x - n) > epsilon)
        {
            x = (x + n / x) / 2;  // 疊代更新公式
        }

        return x;
    }
    ```

**6.枚舉法（Brute Force / Enumeration）**
* 將所有可能的解法全部嘗試一次，選出最優解
* 最直接但效率最差
* 例子：
    ```C#
    for(int num = 1 ; num < 501; num ++)
    {
        if(num % 5 == 0 )
        {
            Console.WriteLine(num + "是5的倍數");
        }
    }
    ```

#### 討論題
👉 在日常生活中有哪些事情可以透過以上的演算法，高效解決問題呢？
👉 這些演算法有哪些適合與不適合的例子嗎?

---
### 1-5 程式設計簡介
#### 重點說明
* 資料結構與演算法最終要「用程式實作」。
* 程式語言只是「表達工具」，邏輯才是核心。

* 程式開發重點：
    * 可讀性（Readability）
    * 效率性
    * 可靠性
    * 維護性

    ![image](https://hackmd.io/_uploads/SJIkx7sy-l.png)

#### 物件導向設計的三大核心概念

| 概念 | 定義 | 生活化比喻 | C# 範例 |
| -------- | -------- | -------- | -------- |
| **封裝（Encapsulation）** | 把資料與操作資料的方法「包」在一起，外部只能透過特定介面操作。實現抽象畫資料型態的概念。 | 手機外殼封起來，使用者只能透過按鍵或App操作，不能直接改晶片   | 使用 `private` 欄位，`public` 方法存取：<br>`csharp\nprivate int balance;\npublic void Deposit(int amount){ balance += amount; }\n` |
| **繼承（Inheritance）** | 子類別可以**繼承父類別的屬性與方法**，並可擴充或改寫   | 「狗」是「動物」的一種，繼承動物的特性（會吃、會睡），但多了「會叫」 | `csharp\nclass Animal { public void Eat() {} }\nclass Dog : Animal { public void Bark() {} }\n`  |
| **多型（Polymorphism）**  | 相同方法名稱在不同物件上可以有**不同的實作** |「畫」這個動作：畫家用筆、工程師用程式畫圖、幼兒用蠟筆，都叫「畫」但方法不同 | `csharp\nclass Shape { public virtual void Draw() {} }\nclass Circle : Shape { public override void Draw() {} }\n` |

#### 其他關鍵名詞

| 概念 | 定義 | 生活化比喻 | C# 範例 |
| -------- | -------- | -------- | -------- |
| **物件（Object）**   | 類別的實例；同時包含資料（屬性）與行為（方法） | 一台具體的手機          | `csharp\nPhone myPhone = new Phone();`                                |
| **類別（Class）**    | 物件的藍圖，用來定義結構與行為         | 手機的設計圖           | `csharp\nclass Phone { public string Model; public void Call(){} }\n` |
| **屬性（Property）** | 描述物件的特徵或狀態              | 手機的顏色、型號、電量      | `csharp\npublic string Color { get; set; }`                           |
| **方法（Method）**   | 物件能做的動作或行為              | 手機能「打電話」「拍照」「充電」 | `csharp\npublic void Call(string number) { ... }`                     |


---
### 額外內容
* 將演算法轉換成程式時，要注意：
    * 控制流程（if, loop）
    * 資料儲存（array, list）
    * 模組化（function）

#### 例子：C# 簡單搜尋演算法
```C#
using System;

class Program
{
    static void Main()
    {
        int[] numbers = { 3, 8, 2, 10, 6 };
        int target = 10;

        int index = Search(numbers, target);

        if (index != -1)
            Console.WriteLine($"找到目標 {target}，位置在索引 {index}");
        else
            Console.WriteLine($"找不到目標 {target}");
    }

    static int Search(int[] arr, int target)
    {
        // 線性搜尋：逐一比對陣列中的每個元素
        for (int i = 0; i < arr.Length; i++)
        {
            if (arr[i] == target)
                return i; // 找到就回傳索引
        }
        return -1; // 沒找到就回傳 -1
    }
}
```
**講解要點**
* Search 方法代表一個演算法，功能是「搜尋資料」
* 陣列（int[] arr）就是資料結構
* 這個方法的時間複雜度是 O(n)，因為最壞情況下要檢查所有元素

#### 改良版：二分搜尋（C# 範例）
```C#
using System;

class Program
{
    static void Main()
    {
        int[] sorted = { 2, 3, 6, 8, 10, 12, 15 };
        int target = 10;

        int index = BinarySearch(sorted, target);

        if (index != -1)
            Console.WriteLine($"找到目標 {target}，位置在索引 {index}");
        else
            Console.WriteLine($"找不到目標 {target}");
    }

    static int BinarySearch(int[] arr, int target)
    {
        int left = 0;
        int right = arr.Length - 1;

        while (left <= right)
        {
            int mid = (left + right) / 2;

            if (arr[mid] == target)
                return mid;
            else if (arr[mid] < target)
                left = mid + 1;
            else
                right = mid - 1;
        }

        return -1;
    }
}
```
**講解要點**
* 這是「二分搜尋法」
* 適用於「已排序的資料」
* 每次比較都可以排除一半的資料 → 時間複雜度 O(log n)
* 可以和前一個線性搜尋範例對比 
    >在第一個範例中，我們用最直接的方式逐一比對每個元素。
    當資料量很小時這樣沒問題，但資料一多就會變慢。
    >第二個範例用二分搜尋的方式，每次排除一半的範圍，
    所以速度提升非常明顯。這就是演算法效率的差別。
    
       
#### 討論題
👉 在學習程式設計時，你覺得「語法」和「邏輯」哪個比較難？為什麼？

---
### 總結
資料結構 ≈ 資料的「容器」

演算法 ≈ 處理資料的「方法」

效能分析 ≈ 評估方法的「效率」

目標：用最有效率的方式處理大量資料

