鄧姚文 ywdeng@mail.knu.edu.tw http://w3.im.knu.edu.tw/~joseph/ 資料結構 第一章:基本概念 鄧姚文 ywdeng@mail.knu.edu.tw http://w3.im.knu.edu.tw/~joseph/
資料結構 資料(Data) 資料結構(Data Structure) 電腦處理的符號 資料之間的邏輯關係 著重問題需求和資料之間的關係 數值(Numerical) 字串(String) 多媒體(Multimedia) 資料結構(Data Structure) 資料之間的邏輯關係 表現方式(Representation) 處理方式(Manipulation) 著重問題需求和資料之間的關係
資料特性 識別(Identification) 順序(Sequential Order) 階層(Hierarchical Structure) 形狀 線性結構(Linear) 樹狀結構(Tree) 圖形結構(Graph)
演算法(Algorithm) 一組可完成特定工作的指令集合 必要條件: 輸入(Input):0~n個資料輸入 輸出(Output):至少一個輸出 明確(Definiteness):清楚而明確 有限(Finiteness):在有限的步驟內結束 有效率(Effectiveness):用紙和筆即可實踐之;可行(Feasible)
範例:找尋最大值 輸入:n個數字 輸出:這n個數字之中的最大值 步驟: 將n個數字排好成一列 令第1個數字為最大值max 若m比max大,則令max的值等於m 輸出max,這n個數字之中的最大值
範例:求函數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)的最大值
演算法的表示方式 自然語言 虛擬碼(Pseudo Code) 流程圖(Flowchart) 結構性較好的程式語言 Pascal、C、C++、Java、C#、… 不要用稀有的語言,以免別人看不懂 演算法(Algorithm)與程式(Program)的差異: 演算法必須在有限步驟內停止,程式未必會停 不停的程式:作業系統、Email Server、Web Server、…
程式撰寫的流程 問題的需求與限制 思考與探索 資料結構與演算法設計 撰寫程式碼 驗證、測試與修改 結果輸出
演算法的效率分析 時間複雜度(Time Complexity) 空間複雜度(Space Complexity) 複雜度的表示法 所需的執行時間 Σ一行敘述的執行次數 × 一行敘述的執行時間 空間複雜度(Space Complexity) 所需的記憶體空間 複雜度的表示法 О、Ω、Θ
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(); }
Big-O 演算法的複雜度 定義: 若且唯若存在兩個正整數 c 和 n0 當 n ≥ n0 時, 意義:Upper Bound 上限
範例:
範例:
時間複雜度分析範例: 循序搜尋(Sequential Search) 最佳狀況 Best Case:1 搜尋目標在陣列一開頭就找到了 最壞狀況 Worst Case:n 找完整個陣列才知搜尋目標不在其中 平均狀況 Average Case:n/2 平均搜尋次數: 若搜尋成功之機率為 p:
循序搜尋 (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;
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!):階乘時間 大
Big-Ω 問題的難易程度 定義: 若且唯若存在兩個正整數 c 和 n0, 當 n ≥ n0 時, 意義:Lower Bound 下限
範例:
Θ 最佳解(Optimal Solution) 定義: 若且唯若存在三個正整數 c1、c2、n0, 當 n ≥ n0 時
二元搜尋 (Binary Search) 輸入: 輸出: n 筆已排序資料(從小排到大) 欲尋找之資料 target 1 2 3 4 5 6 7 8 9 找 5 大 小 中
二元搜尋(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;
二元搜尋(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)
二元搜尋(Binary Search) 時間複雜度:O(log n) 搜尋範圍從 n 筆資料開始 每完成一次比較,搜尋範圍縮小一半 停止的時機: 找到目標 搜尋範圍的大小<1(Worst Case) n 連續除以 2,連除 m 次之後 < 1
費氏數列(Fibonacci Series) 問題:給定一個 n 值,求解費氏數列第 n 項的值。
費氏數列(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)
費氏數列(Fibonacci Series) 遞迴版時間複雜度分析
費氏數列(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)
Tower of Hanoi
Tower of Hanoi
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); }
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); }
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
Tower of Hanoi 時間複雜度分析