鄧姚文 ywdeng@mail.knu.edu.tw http://w3.im.knu.edu.tw/~joseph/ 資料結構 第一章：基本概念 鄧姚文 ywdeng@mail.knu.edu.tw http://w3.im.knu.edu.tw/~joseph/

Presentation on theme: "鄧姚文 ywdeng@mail.knu.edu.tw http://w3.im.knu.edu.tw/~joseph/ 資料結構 第一章：基本概念 鄧姚文 ywdeng@mail.knu.edu.tw http://w3.im.knu.edu.tw/~joseph/"— Presentation transcript:

1 鄧姚文 ywdeng@mail.knu.edu.tw http://w3.im.knu.edu.tw/~joseph/
資料結構 第一章：基本概念 鄧姚文

2 資料結構 資料（Data） 資料結構（Data Structure） 電腦處理的符號 資料之間的邏輯關係 著重問題需求和資料之間的關係
數值（Numerical） 字串（String） 多媒體（Multimedia） 資料結構（Data Structure） 資料之間的邏輯關係 表現方式（Representation） 處理方式（Manipulation） 著重問題需求和資料之間的關係

3 資料特性 識別（Identification） 順序（Sequential Order）
階層（Hierarchical Structure） 形狀 線性結構（Linear） 樹狀結構（Tree） 圖形結構（Graph）

4 演算法（Algorithm） 一組可完成特定工作的指令集合 必要條件： 輸入（Input）：0~n個資料輸入
輸出（Output）：至少一個輸出 明確（Definiteness）：清楚而明確 有限（Finiteness）：在有限的步驟內結束 有效率（Effectiveness）：用紙和筆即可實踐之；可行（Feasible）

5 範例：找尋最大值 輸入：n個數字 輸出：這n個數字之中的最大值 步驟： 將n個數字排好成一列 令第1個數字為最大值max
若m比max大，則令max的值等於m 輸出max，這n個數字之中的最大值

6 範例：求函數f(x)的最大值 輸入：函數f(x) 輸出：f(x)的最大值 步驟： 令max為最小的實數 從0開始逐一嘗試每一個實數x
令y=f(x) 若y比max大，令max的值等於y 令z=f(-x) 若z比max大，令max的值等於z 輸出max，此即f(x)的最大值

7 演算法的表示方式 自然語言 虛擬碼（Pseudo Code） 流程圖（Flowchart） 結構性較好的程式語言
Pascal、C、C++、Java、C#、… 不要用稀有的語言，以免別人看不懂 演算法（Algorithm）與程式（Program）的差異： 演算法必須在有限步驟內停止，程式未必會停 不停的程式：作業系統、 Server、Web Server、…

8 程式撰寫的流程 問題的需求與限制 思考與探索 資料結構與演算法設計 撰寫程式碼 驗證、測試與修改 結果輸出

9 演算法的效率分析 時間複雜度（Time Complexity） 空間複雜度（Space Complexity） 複雜度的表示法
所需的執行時間 Σ一行敘述的執行次數 × 一行敘述的執行時間 空間複雜度（Space Complexity） 所需的記憶體空間 複雜度的表示法 О、Ω、Θ

10 Order of Magnititude O(n) O(n3) for (x = 0; x < n; x++) {
do_something(); } for (x = 0; x < n; x++) { for (y = 0; y < n; y++) { for (z = 0; z < n; z++) { do_something(); } O(n2) for (x = 0; x < n; x++) { for (y = 0; y < n; y++) { do_something(); }

11 Big-O 演算法的複雜度 定義： 若且唯若存在兩個正整數 c 和 n0 當 n ≥ n0 時， 意義：Upper Bound 上限

12 範例：

13 範例：

14 時間複雜度分析範例： 循序搜尋（Sequential Search）
最佳狀況 Best Case：1 搜尋目標在陣列一開頭就找到了 最壞狀況 Worst Case：n 找完整個陣列才知搜尋目標不在其中 平均狀況 Average Case：n/2 平均搜尋次數： 若搜尋成功之機率為 p：

15 循序搜尋 （Sequential Search）
int sequential_search(int data[], int target, int n) { int i; for (i = 0; i < n; i++) { if (target == data[i]) { return i; } return -1;

16 Big-O 順序 O(1)：常數時間（Constant Time） O(log2n)：次線性時間（Sub-linear Time）
O(n)：線性時間（Linear Time） O(nlog2n)： n 對數時間 O(n2)：平方時間（Quadratic Time） O(n3)：立方時間（Cubic Time） O(2n)：指數時間（Exponential Time） O(n!)：階乘時間 大

17 Big-Ω 問題的難易程度 定義： 若且唯若存在兩個正整數 c 和 n0， 當 n ≥ n0 時， 意義：Lower Bound 下限

18 範例：

19 Θ 最佳解（Optimal Solution）
定義： 若且唯若存在三個正整數 c1、c2、n0， 當 n ≥ n0 時

20 二元搜尋 （Binary Search） 輸入： 輸出： n 筆已排序資料（從小排到大） 欲尋找之資料 target
1 2 3 4 5 6 7 8 9 找 5 大 小 中

21 二元搜尋（Binary Search） int binary_search(int data[], int n, int target) {
int left = 0, right = n-1, mid; while (left <= right) { mid = (left + right) / 2; if (target == data[mid]) { return mid; } else if (target > data[mid]) { left = mid + 1; } else { right = mid - 1; } return -1;

22 二元搜尋（Binary Search） 遞迴版（Recursive）
int bin_search(int data[], int left, int right, int target) { int mid = (left + right) / 2; if (left > right) return -1; if (target == data[mid]) return mid; if (target > data[mid]) { return bin_search(data, mid+1, right, target); } else { return bin_search(data, left, mid-1, target); } 用法： bin_search(data, 0, n-1, target)

23 二元搜尋（Binary Search） 時間複雜度：O(log n) 搜尋範圍從 n 筆資料開始 每完成一次比較，搜尋範圍縮小一半
停止的時機： 找到目標 搜尋範圍的大小<1（Worst Case） n 連續除以 2，連除 m 次之後 < 1

24 費氏數列（Fibonacci Series）
問題：給定一個 n 值，求解費氏數列第 n 項的值。

25 費氏數列（Fibonacci Series） 遞迴版
int fibon(int n) { if (n == 0) return 0; if (n == 1) return 1; return fibon(n-1) + fibon(n-2); } 時間複雜度：O(2n/2)

26 費氏數列（Fibonacci Series） 遞迴版時間複雜度分析

27 費氏數列（Fibonacci Series） 迴圈版
int fibonacci(int n) { int fn, fn_1 = 1, fn_2 = 0, i; if (n < 2) return n; for (i = 2; i <= n; i++) { fn = fn_1 + fn_2; fn_2 = fn_1; fn_1 = fn; } return fn; 時間複雜度：O(n)

28 Tower of Hanoi

29 Tower of Hanoi

30 Tower of Hanoi 宣告與用法 #define PEG_A "PEG_A" #define PEG_B "PEG_B"
#define PEG_C "PEG_C" int main(int argc, char* argv[]) { … hanoi_move(n, PEG_A, PEG_B, PEG_C); }

31 Tower of Hanoi 主要邏輯 void hanoi_move(int n, char* from, char* to, char* via) { if (n == 1) { printf("Move ring 1 from %s to %s\n", from, to); } else { hanoi_move(n-1, from, via, to); printf("Move ring %d from %s to %s\n", n, from, to); hanoi_move(n-1, via, to, from); }

32 Tower of Hanoi 執行結果 1: Move ring 1 from PEG_A to PEG_B
2: Move ring 2 from PEG_A to PEG_C 3: Move ring 1 from PEG_B to PEG_C 4: Move ring 3 from PEG_A to PEG_B 5: Move ring 1 from PEG_C to PEG_A 6: Move ring 2 from PEG_C to PEG_B 7: Move ring 1 from PEG_A to PEG_B

33 Tower of Hanoi 時間複雜度分析