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

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

**例子**

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

#### 資料特性：電腦如何看待資料
1. 基本資料型態：
* 不能拆解的最基本型態，電腦底層知道如何儲存它們
* 例如：C#的整數(int)、浮點數(float)、字元(char)...
2. 結構化資料型態：
* 由多個基本資料組合而成，也就是「資料容器」的概念
* 例如：字串(string)、陣列(array)、指標(pointer)、串列(list)、檔案(file)

    ● 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. 效率高（執行時間與資源消耗合理）

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

#### 例子：「泡咖啡」的步驟就是一個演算法。

步驟明確（加水 → 加粉 → 攪拌）
有結果（得到咖啡）
若中間無限攪拌，就不算好演算法。

#### 討論題
👉 日常生活中有什麼事情可以被你定義成一個「演算法」？
👉 生活中有沒有經驗「照順序做事很慢，換一個方法就快很多」？

---
### 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²) 好很多 |


💡小提示：
* 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）

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

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

**5. 疊代法（Iterative Method）**
* 「重複執行某個步驟直到達成條件」 的方法
* 例子：「牛頓疊代法」(Newton’s Iteration Method)

    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）**
* 將所有可能的解法全部嘗試一次，選出最優解
* 最直接但效率最差
* 例子：

    for(int num = 1 ; num < 501; num ++)
    {
        if(num % 5 == 0 )
        {
            Console.WriteLine(num + "是5的倍數");
        }
    }

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

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

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


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

| 概念 | 定義 | 生活化比喻 | 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# 簡單搜尋演算法

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# 範例）

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)
* 可以和前一個線性搜尋範例對比
>在第一個範例中，我們用最直接的方式逐一比對每個元素。
當資料量很小時這樣沒問題，但資料一多就會變慢。
>第二個範例用二分搜尋的方式，每次排除一半的範圍，
所以速度提升非常明顯。這就是演算法效率的差別。

#### 討論題
👉 在學習程式設計時，你覺得「語法」和「邏輯」哪個比較難？為什麼？

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

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

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

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