## 二、 程式的創建流程（瀑布模型）

程式開發通常遵循以下步驟：

1. **需求收集**：確定系統所需的功能、目標與限制。
2. **系統分析**：深入理解需求，定義系統必須達成的標準。
3. **設計**：
* **架構設計**：確立系統的整體結構與組件關係。
* **細節設計**：決定具體的資料結構、資料型態和演算法。
* **介面設計（可選）**：規劃使用者與系統的互動方式。
4. **編碼與調整**：將設計實現為程式碼，並進行初步優化。
5. **驗證與測試**：確保程式功能正確，符合所有需求。
6. **維護與演進**：持續進行錯誤修正、功能改進和系統升級。

-----

## 三、 演算法（Algorithm）

### 1\. 定義

演算法是**一組有限且定義清晰的指令**，用於完成特定任務或解決特定問題。

### 2\. 特性

演算法必須滿足以下五個特性：

* **輸入 (Input)**：具備零個或多個輸入。
* **輸出 (Output)**：至少產生一個或多個輸出。
* **確定性 (Definiteness)**：每條指令都必須清晰、無歧義。
* **有限性 (Finiteness)**：演算法必須在有限的步驟後終止。
* **有效性 (Effectiveness)**：每個指令都必須是基本、可行且可在有限時間內完成的。

-----

## 四、 遞迴（Recursion）

### 1\. 定義

遞迴是指在程式中，一個函數**直接或間接呼叫自身**的機制。

### 2\. 種類

* **直接遞迴 (Direct Recursion)**：函數 $A$ 直接呼叫函數 $A$。
* **間接遞迴 (Indirect Recursion)**：函數 $A$ 呼叫函數 $B$，而函數 $B$ 再呼叫函數 $A$。
* **尾遞迴 (Tail Recursion)**：遞迴呼叫是函數中最後一個執行的操作。

### 3\. 優點與缺點

| 項目 | 優點 | 缺點 |
| :--- | :--- | :--- |
| **程式碼** | 邏輯清晰，易於設計與閱讀，程式碼簡潔。 | 執行效率較低，且需要消耗較多的**堆疊空間**（Stack Space）來儲存中間狀態。 |

### 4\. 常見應用

* **數學問題**：如階乘 ($N!$)、費氏數列 (Fibonacci Sequence)。
* **資料結構**：如二元樹的遍歷、快速排序 (Quick Sort)。
* **經典問題**：如河內塔 (Towers of Hanoi)、平面分割問題。

-----

## 五、 資料型態與抽象資料型態 (ADT)

### 1\. 資料型態 (Data Type)

資料型態是一組**物件集合**，以及定義在這些物件上的**操作集合**。

* **範例（整數型態）**：
* **物件集合**：所有整數 (如 ..., -2, -1, 0, 1, 2, ...)。
* **操作集合**：加、減、乘、除、比較運算 (如 \>、\< 等)。

### 2\. 抽象資料型態 (Abstract Data Type, ADT)

ADT 是一種資料型態，它將**物件的規格 (Specification)** 及其**操作**，與其**具體表示 (Representation)** 及**操作實現 (Implementation)** **分離**。

* **ADT 的重點在於「做什麼」(What) 而非「如何做」(How)。**
* **範例：堆疊 (Stack) ADT**
* **規格**：定義元素的集合、LIFO（後進先出）特性、基本操作 (如 push, pop)。
* **實現**：底層可以選擇使用**陣列 (Array)** 或**鏈結串列 (Linked List)** 來實作堆疊。

-----

## 六、 效能分析與測量

* **效能測量 (Performance Measurement)**：
* **依賴機器**：在特定硬體和軟體環境下，實際測量程式的執行時間和資源消耗。
* **效能分析 (Performance Analysis)**：
* **不依賴機器**：主要關注演算法的**空間複雜度**與**時間複雜度**。

### 1\. 空間複雜度 (Space Complexity)

衡量演算法執行所需的記憶體空間。包含：

* **程式碼空間**：儲存程式指令的空間。
* **變數空間**：儲存常數和變數所需的空間。
* **遞迴堆疊空間**：遞迴呼叫所需的堆疊空間。

### 2\. 時間複雜度 (Time Complexity)

衡量演算法執行所需的**基本運算步驟數**（Step Count），用來估計執行時間。

* **步驟計算方法**：透過計算每條指令的**執行次數 (頻率)**，並累加所有指令的總步數。

-----

## 七、 演算法的漸進符號 (Asymptotic Notations)

### $O$ 符號（大 O 符號, Big Oh Notation）

* **定義**：表示函數的**漸進上界**。
若存在正的常數 $c$ 和 $n_0$，使得對於所有 $n \ge n_0$，皆有 $f(n) \le c \cdot g(n)$ 成立，則稱 $f(n) = O(g(n))$。

* **用途**：用來描述演算法在**最壞情況**下的執行時間。

* **範例**：

* $2n + 3 = O(n)$，因為當 $n \ge 3$ 時，$2n + 3 \le 3n$（取 $c=3, n_0=3$）。
* $3n^2 + 2n + 3 = O(n^2)$，因為當 $n \ge 3$ 時，$3n^2 + 2n + 3 \le 4n^2$（取 $c=4, n_0=3$）。

### 常見的時間複雜度與成長順序

| 符號表示 | 名稱 | 成長速度 (由慢到快) |
| :--- | :--- | :--- |
| $O(1)$ | 常數時間 (Constant Time) | 1. $O(1)$ (常數) |
| $O(\log n)$ | 對數時間 (Logarithmic Time) | 2. $O(\log n)$ (對數) |
| $O(n)$ | 線性時間 (Linear Time) | 3. $O(n)$ (線性) |
| $O(n \log n)$ | 線性對數時間 | 4. $O(n \log n)$ |
| $O(n^2)$ | 平方時間 (Quadratic Time) | 5. $O(n^2)$ (平方) |
| $O(n^3)$ | 立方時間 (Cubic Time) | 6. $O(n^3)$ (立方) |
| $O(2^n)$ | 指數時間 (Exponential Time) | 7. $O(2^n)$ (指數) |
| $O(n!)$ | 階乘時間 (Factorial Time) | 8. $O(n!)$ (階乘) |

-----

## 八、 排序演算法簡介

### 1\. 堆疊排序 (Heap Sort)

* **核心概念**：利用堆積樹 (Heap) 的特性。每次將目前最大（或最小）的元素移到正確的位置，然後將堆積的大小減 1，重複此過程。

### 2\. 快速排序 (Quick Sort)

* **核心概念**：採用**分治法 (Divide and Conquer)**。選擇一個元素作為**基準點 (Pivot)**，將所有小於基準點的元素移到左邊，大於基準點的元素移到右邊，然後對左右兩側子序列遞迴地進行排序。

-----

## 九、 遞迴範例：河內塔 (Towers of Hanoi)

* **遞迴函式**：

    Hanoi(N, A, B, C):
        if N > 0:
            // 1. 將 N-1 個盤子從 A 移到 B (輔助柱)
            Hanoi(N-1, A, C, B)
            
            // 2. 將第 N 個盤子從 A 移到 C (目標柱)
            Move_Disk(A, C)
            
            // 3. 將 N-1 個盤子從 B 移到 C (目標柱)
            Hanoi(N-1, B, A, C)

* **步驟數 (時間複雜度)**：
* 河內塔問題所需的總移動步數為 $2^N - 1$。
* 其時間複雜度為 $O(2^N)$。

-----

## 堆疊 (Stack) 的 Python 實作 (使用列表 List)

# 初始化一個空棧 (Python 列表作為底層結構)
stack = []

# Push 函式：將元素推入棧頂 (使用 list 的 append 方法)
def Push(s, element):
    s.append(element)
    print(f"Pushed {element} to stack")

# Pop 函式：從棧頂彈出元素 (使用 list 的 pop 方法)
def Pop(s):
    # 檢查是否為空棧 (Underflow)
    if not s: # 相當於 len(s) == 0
        print("Stack is empty (Underflow)")
        return None
    else:
        element = s.pop()
        print(f"Popped {element} from stack")
        return element

# 範例
# Push(stack, 10)
# Pop(stack)
# Pop(stack)