1-4-2 时间复杂度.ppt

資料結構 第1章　導論 1-1　認識資料結構 資料結構指的是資料在記憶體空間的儲存方式及存取方式，演算法指的是處理資料的流程，而程式 = 資料結構 + 演算法 。 範例1.1：[找出最大數] main() { int largest = 0; if (25 largest) largest = 25; if (30 largest) largest = 30; if (18 largest) largest = 18; if (7 largest) largest = 7; if (10 largest) largest = 10; printf(最大數為%d, largest); } 範例1.2：[找出最大數] 01:main() 02:{ 03: int i; 04: int list[5] = {25, 30, 18, 7, 10}; 05: int largest = 0; 06: for(i = 0; i 5; i++) 07: if (list[i] largest) largest = list[i]; 08: printf(最大數為%d, largest); 09:} 1-2　認識演算法 演算法必須符合下列五個條件： 輸入 (input) 輸出 (output) 明確性 (definiteness) 有效性 (effectiveness) 有限性 (finiteness) 1-2-1　構思演算法 階段一 階段二 嘗試錯誤法 (try and error) 反推法 (backward) 逐步細分法 (stepwise refinement) 類推法 階段三 階段四 範例1.3：使用 [類推法] 構思 [n個正整數中的最大數] 演算法。 1. 2. 3. 4. 5. int find_largest(int list[], int n) { int i; int largest = 0; for(i = 0; i n; i++) if (list[i] largest) largest = list[i]; return(largest); } 1-2-2　演算法的結構 序列 (sequence) 決策 (decision) 重覆 (repetition) 1-2-3　演算法的表示方式 流程圖 虛擬碼 1-2-4　反覆與遞迴 範例1.7：[(n階層)] 使用反覆的方式計算n!，其公式如下： 當n = 0時，f(n) = n! = 0! = 1 當n 0時，f(n) = n! = n x (n - 1) x … x 3 x 2 x 1 int factorial(int n) { int result = 1; if (n == 0) return 1; while(n 0){ result = result * n; n = n - 1; } return result; } 範例1.8：[ (n階層)] 使用遞迴的方式計算n!，其公式如下： 當n = 0時，f(n) = n! = 0! = 1 當n 0時，f(n) = n! = n x f(n - 1) int factorial(int n) { if (n == 0) return 1; else return (n * factorial(n - 1)); } 1-3　抽象資料型別 (ADT) 抽象資料型別 (ADT，abstract data type) 指的是將物件的規格及其相關運算的規格，與物件的表示方式及其相關運算的實作方式分隔開來，以提供更便利的形式讓使用者存取資料，而不涉及資料的實際儲存細節或實作細節。 範例1.11：設計一個 [抽象資料型別Positive_Integer]，這是正整數及其相關運算的集合。 ADT: Positive_Integer Objects: Integers between 1 to the maximum integer on the computer Functions: for all x, y belongs Positive_Integer, and where +, -, *, / are the usual integer operations Positive_Integer Add(x, y) → if ((x