資料結構 第1章　導論.

Presentation on theme: "資料結構 第1章　導論."— Presentation transcript:

1 資料結構 第1章　導論

2 1-1　認識資料結構 資料結構指的是資料在記憶體空間的儲存方式及存取方式，演算法指的是處理資料的流程，而程式 = 資料結構 + 演算法 。

3 範例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); }

4 範例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:}

5 1-2 認識演算法 演算法必須符合下列五個條件： 輸入 (input) 輸出 (output) 明確性 (definiteness)
1-2　認識演算法 演算法必須符合下列五個條件： 輸入 (input) 輸出 (output) 明確性 (definiteness) 有效性 (effectiveness) 有限性 (finiteness)

6 1-2-1 構思演算法 階段一 階段二 階段三 階段四 嘗試錯誤法 (try and error) 反推法 (backward)
1-2-1　構思演算法 階段一 階段二 嘗試錯誤法 (try and error) 反推法 (backward) 逐步細分法 (stepwise refinement) 類推法 階段三 階段四

7 範例1.3：使用 [類推法] 構思 [n個正整數中的最大數] 演算法。

8 2.

9 3.

10 4.

11 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); }

12 1-2-2　演算法的結構 序列 (sequence) 決策 (decision) 重覆 (repetition)

13 1-2-3　演算法的表示方式 流程圖

14 虛擬碼 instruction 1 instruction 2 … instruction n
if (condition) then one set of instructions else another set of instructions while (condition) one set of instructions end while

15 1-2-4 反覆與遞迴 範例1.7：[(n階層)] 使用反覆的方式計算n!，其公式如下：
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;

16 範例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)); }

17

18 1-3　抽象資料型別 (ADT) 抽象資料型別 (ADT，abstract data type) 指的是將物件的規格及其相關運算的規格，與物件的表示方式及其相關運算的實作方式分隔開來，以提供更便利的形式讓使用者存取資料，而不涉及資料的實際儲存細節或實作細節。

19 範例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 + y) <= INT_MAX) return x + y else return INT_MAX Positive_Integer Subtract(x, y) → if ((x - y) <= 0) return else return x - y Positive_Integer Increase(x) → if ((x + 1) <= INT_MAX) return x else return INT_MAX Positive_Integer Decrease(x) → if ((x - 1) <= 0) return else return x - 1 End Positive_Integer

20 1-4　程式的效能分析 空間複雜度 (space complexity) 時間複雜度 (time complexity)

21 1-4-1 空間複雜度 固定記憶體空間 (fixed space) 變動記憶體空間 (variable space)
1-4-1　空間複雜度 固定記憶體空間 (fixed space) 變動記憶體空間 (variable space) 範例1.12：[兩個整數的總和] 分析下列程式的空間複雜度為何？ int add(int a, int b) { return (a + b); }

22 範例1.13：[n個整數的總和] 分析下列程式的空間複雜度為何？
int sum(int list[], int n) { int i; int result = 0; for(i = 0; i < n; i++) result = result + list[i]; return result; }

23 1-4-2　時間複雜度 時間複雜度 (time complexity) 指的是程式執行完畢所需的時間，為編譯時間 (compile time) 與執行時間 (execution time) 的總和。

24 範例1.15：[n個整數的總和] 分析範例1.13的時間複雜度為何？
敘述 s/e 頻率 程式步驟個數 int sum(int list[], int n) { int i; int result = 0; 1 for(i = 0; i < n; i++) n + 1 result = result + list[i]; n return result; } 總計 2n + 3 表1.2分析範例1.13的程式步驟個數

25 範例1.16：[n個整數的總和] 分析範例1.14的時間複雜度為何？
敘述 s/e 頻率 程式步驟個數 int sum(int list[], int n) { if (n) 1 n + 1 return (sum(list, n - 1) + list[n - 1]); n return 0; } 總計 2n + 2 表1.3分析範例1.14的程式步驟個數

26 1-4-3　漸進符號 (O、Ω、Θ) 理論上限O()(唸做“Big-Oh”)：f(n) = O(g(n)) 若且為若存在正的常數c和n0，對所有n, n ≥ n0時，f(n) ≤ cg(n) 均成立，例如f(n) = 2n + 3 = O(n)，f(n) = 5n2 + 2n = O(n2) 。 理論下限Ω()(唸做“Omega”)：f(n) = Ω(g(n)) 若且為若存在正的常數c和n0，對所有n, n ≥ n0時，f(n) ≥ cg(n) 均成立，例如f(n) = 2n + 3 = Ω(n)，f(n) = 5n2 + 2n = Ω(n2) 。 理論上下限Θ()(唸做“Theta”)：f(n) = Θ(g(n)) 若且為若存在正的常數c1、c2和n0，對所有n, n ≥ n0時，c1g(n) ≤ f(n) ≤ c2g(n) 均成立，例如f(n) = 2n + 3 = Θ(n)，f(n) = 5n2 + 2n = Θ(n2) 。

27 範例1.19：證明當f(n) = amnm + … + a1n + a0時，f(n) = O(nm)。

28 範例1.20：分析3 * 2n + n2 + n的O() 為何？ 解答： f(n) = 3 * 2n + n2 + n = O(2n)，因為存在正的常數c = 4和n0 = 5，對所有n, n ≥ 5時，f(n) ≤ 4 * 2n均成立。

29 範例1.25：分析下列程式的O() 為何？ for(i = 0; i < n; i++) x++; 範例1.26：分析下列程式的O() 為何？ for(i = n; i > 0; i = i / 2) x++; 範例1.27：分析下列程式的O() 為何？ for(i = 0; i < n; i++) for(j = 0; j < n; j++) x++;