資料結構與演算 第一章　基本概念.

Presentation on theme: "資料結構與演算 第一章　基本概念."— Presentation transcript:

1 資料結構與演算 第一章　基本概念

2 基本概念 1.1　資料結構、演算法 1.2　資料結構與演算法 1.3　簡單的資料結構 1.4　演算法初探 1.5　演算法的效率分析

3 1.1 資料結構、演算法 「資料結構」(data structure): 在電腦中有效率地存放資料，使其方便處理的學問；
1.1　資料結構、演算法 「資料結構」(data structure): 在電腦中有效率地存放資料，使其方便處理的學問； 「演算法」(algorithm): 探討解決問題的策略。 兩者相輔相成!

4 Program Language (程式語言)
= Data Structure (資料結構) + Algorithm (演算) Program Language (程式語言)

5 1.2　資料結構與演算法 電腦處理的對象稱為「資料」(data)，泛指所有輸入至電腦中，即將、正在或已經被電腦程式處理的符號總稱；包括了數值(numerical) 資料、字串 (string) 資料等等，乃至於目前多媒體 (multimedia) 軟體所處理的影像、聲音、視訊等多媒體資料。

6 1.2　資料結構與演算法 當這些資料集合在一起時，會因處理需求的不同而存在一種或多種彼此之間的特定關係，這些資料之間的邏輯關係，就稱為結構 (structure)。 研究資料的邏輯關係，探討這些邏輯關係在電腦中的表示(representation) 和處理 (manipulation) 方式，即為「資料結構」。

7 1.3 簡單的資料結構 生活中常見的資料相互關係： (1)校園中有一群人； (2)每個中華民國國民皆有唯一的身分證字號；
1.3　簡單的資料結構 生活中常見的資料相互關係： (1)校園中有一群人； (2)每個中華民國國民皆有唯一的身分證字號；  (3)每位同學在班上皆有唯一的座號、在學校皆有唯一的學號； (4)在大學中的科系有系別、年級別、甚至於班別；

8 1.3 簡單的資料結構 生活中常見的資料相互關係：
1.3　簡單的資料結構 生活中常見的資料相互關係： (5)排隊的時候，我們可能只關心排在前一位的是誰？有時可能還在意排在自己前面的共有多少人？ (6)外國旅行時，各景點間是否有班機直飛？ (7)上網尋找資料，網頁間的鏈結，將網頁連結成複雜的全球性的網絡(world-wide web)。

9 1.4　演算法初探 Horowitz, Sahni 和 Mehta ，給予演算法的明確定義： 演算法是一組可完成特定工作的指令集合，並且所有的演算法都需滿足下列條件： (1) 輸入 (input)：可以有多個其甚至是沒有輸入； (2) 輸出 (output)：至少產生一個輸出； (3) 明確(definiteness)：每個指令都清楚明確； (4) 有限(finiteness)：在任何情況下，如果逐步追蹤演算 法的每個指令，演算法會在有限的步驟內結束； (5) 有效率(effectiveness)：原則上每個指令都需 基本到人只需紙和筆即可實踐之，並且每個指令的運算不止如條件(3)般明確而已，還必須是可實行的。

10 1.4.1程式撰寫流程 撰寫程式解決問題流程圖 問題的需求或限制 思考與探索 資料結構與演算法設計 程式撰寫 驗証、測試與修善 數學証明
結果輸出 撰寫程式解決問題流程圖

11 範例：挑選排序法 (Selection sort)
思考與探索： 欲將整數由小至大排序，可把數字小者放在左邊，數字大者放在右邊，… 挑出所有資料中最小者，做為左邊第一個資料，接著再挑出剩下資料中最小者，放在左邊做為第二個資料，依此類推，直至全部資料都排列完成。 若所有資料共計 n 個，則會執行n次挑出最小的運算，其第 i 次的運算，即為挑出未排序資料中最小者，其結果做為第 i 個資料。

12 挑選排序法 (Selection sort)
11, 7, 14, 1, 5, 9, 10 1, 7, 14, 11, 5, 9, 10 1, 5, 14, 11, 7, 9, 10 1, 5, 7, 11, 14, 9, 10 1, 5, 7, 9, 14, 11, 10 1, 5, 7, 9, 10, 11, 14 Input Output

13 範例：挑選排序法 (Selection sort)演算法
輸入：data[0], data[1], data[2], …, data[n-1]，共 n 筆整數資料 輸出：data[0], data[1],…, data[n-1]；其中 若i<j，則data[i]data[j]，0i<jn 方法： (用虛擬碼Pseudo code表示) for (i=0; i<n; i++) { 挑出data[i]至data[n-1]中最小者：data[min] 將data[i] 和 data[min] 對調 }

14 範例：挑選排序法 (Selection sort)程式
void SelectionSort(int data[], int n) { int i, j; int min, temp; for (i=0; i<n; i++) { // 挑出data[i]至data[n-1]中最小者：data[min] min = i; for (j=i+1; j<n; j++) if (data[j]<data[min]) min = j; // 將data[i] 和 data[min] 對調 temp = data[i]; data[i] = data[min]; data[min] = temp; }

15 程式的驗証、測試與修繕 數學証明―最佳的驗証；比較困難。 測試―輸入大量各式資料測試之。
若此為提供他人的程式，還應考慮輸入正確性(input validation)；若資料量非常大，則資料儲存用的陣列，宜用動態配置的技巧宣告使用

16 測試 selectionsort 的程式 int main() { int i, n=10, c[50]; // Input data
for (i=0; i<n; i++) scanf("%d ", &c[i]); // sort SelectionSort(c, n); // Output Result printf("%d %d \n", i, c[i]); system("pause"); return 0; }

17 習 題 若資料是逐漸新增的方式加入資料，請寫一程式，當資料輸入後，立即就將資料依由小至大排好順序。 插入排序法程式範例說明

18 插入排序法 (Insertion sort)
11, 7, 14, 1, 5, 9, 10 11 7, 11 7, 11, 14 1, 7, 11, 14 1, 5, 7, 11, 14 1, 5, 7, 9, 11, 14 1, 5, 7, 9, 10, 11, 14

19 練習 寫一程式，將輸入正整數x，輸出x是否為質數。

20 輸入正整數x，輸出x是否為質數 流程圖

21 輸入正整數x，輸出x是否為質數 演算法 檢查質數的步驟： 1. 若 x < =1，則傳回 x 不是質數。
4. 從 i=3 到 sqrt(x) 間格 2 若 x 是 i 的倍數，則傳回 x 不是質數。 5. 傳回 x 是質數。

22 檢查質數的程式 #define TRUE 1 #define FALSE 0 int prime(int x) { int i;
// 檢查質數的步驟： // 1. 若 x < =1，則傳回 x 不是質數。 if (x<=1) return FALSE; // 2. 若 x <= 3，則傳回 x 是質數。 if (x<=3) return TRUE; // 3. 若 x 是 偶數，則傳回 x 不是質數 。 if (x%2==0) return FALSE; // 4. 從 i=3 到 sqrt(x) 間格 2 for (i=3; i<=sqrt(x); i+=2){ // 若 x 是 i 的倍數，則傳回 x 不是質數。 if (x%i==0) return FALSE; } // 5. 傳回 x 是質數。 return TRUE; 檢查質數的程式

23 測試 prime 的程式 #include <stdio.h> #include <stdlib.h>
#include <math.h> int main() { int n; // Input a positive integer printf("請輸入一正整數： "); scanf("%d", &n); // test prime number & output result if (prime(n)==TRUE) printf("\n %d 是質數！\n\n",n); else printf("\n %d 不是質數！\n\n",n); // Pause system("pause"); } 測試 prime 的程式

24 1.4.2 遞迴演算法 程序呼叫 void tt() { } 程序呼叫時流程的轉換 SS(int data,int n) { }
void SS(int data[],int n) { } SS(int data,int n) 程序呼叫時流程的轉換

25 1.4.2 遞迴演算法 直接遞迴 (direct recursion)：當程序執行完成前呼叫了自己這個程序。 程序呼叫時流程的轉換 {
…void SS(int data[],int n) { } void SS(int data[],int n) { } SS(int data[],int n) 程序呼叫時流程的轉換

26 1.4.2 遞迴演算法 間接遞迴 (indirect recursion) ：在程序執行完成前呼叫了其它會再度引用到自己的程序。
void SS(int data[],int n) { yy() } void TT() { SS(int data[],int n) } void yy() { TT() } 程序呼叫時流程的轉換

27 1.4.2 遞迴演算法 在設計遞迴程式時，切記終結條件 (termination condition) 的設立，否則易造形成無窮迴圈 。
void RS() { RS(); } void RS() { RS(); } void RS() { RS(); } void RS() { RS(); }

28 程式1-2 計算階乘 階乘的計算即可用遞迴的概念詮釋，請看： 於是可以寫一個計算階乘的程序 F(int n)，
它接受傳入的整數 n，傳回 n*F(n-1) int F(int n) { if (n ==1) return 1; return n*F(n-1); }

29 遞迴練習 輸入正整數n，輸出費氏(Fibonacci)數列的第0個至第n個。
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …

30 費氏(Fibonacci)數列 程式 #define ERROR -1 int Fib(int n) {
if (n<0) return ERROR; // n=0 if (n==0) return 0; // n=1 if (n==1) return 1; // n>=2 return Fib(n-1)+Fib(n-2); }

31 費氏(Fibonacci)數列 測試程式 #include <stdio.h>
#include <stdlib.h> int main() { int n, i; // Input a positive number printf("Input a positive integer:", n); scanf("%d",&n); // output Fibnacci number from 0 to n for (i=0; i<=n; i++) printf("Fib(%d)= %d \n", i, Fib(i)); // pause system("pause"); }

32 產生排列 (Permutation)

33 排列(permutation) 1 12, 21 123, 132, 213, 231, 312, 321 4123, 4132, 4213, 4231, 4312, 4321 3124, 3142, 3214, 3241, 3412, 3421 2134, 2143, 2314, 2341, 2413, 2431 1234, 1243, 1324, 1342, 1423, 1432

34 排列(permutation) k n 1 2 3 4 1234, 1243, 1324, 1342, 1423, 1432 2134, 2143, 2314, 2341, 2413, 2431 3124, 3142, 3214, 3241, 3412, 3421 4123, 4132, 4213, 4231, 4312, 4321

35 產生排列演算法 void perm(char c[], int k, int n) { // 產生 c[k],...,c[n] 的所有排列
if (k == n) { // 終結條件成立時(只有1個字元)輸出此項排列 } else {// 讓c[k]固定不動，求 perm(c[],k+1,n) //讓c[k]~c[n]輪流當c[k] //產生 c[k+1],…,c[n]的所有排列 //還原 原字元順序

36 產生排列程式 void perm(char c[], int k, int n) { // 產生 c[k],...,c[n] 的所有排列
if (k == n) { //終結條件成立時(只有1個字元)輸出此項排列 for (int i = 0; i < n; i++) cout << c[i] << " "; cout << endl; } else { // 讓c[k]固定不動，求 perm(c[], k+1, n) for (i=k; i<n; i++) { //讓c[k]~c[n]輪流當c[k] swap(c[k], c[i]); //產生a[k+1],…,a[n]的所有排列 perm(c,k+1,n); //還原 字元順序

37 程式1-3 產生排列 void perm(char c[], int k, int n)
{ // 產生 c[k],...,c[n-1] 的所有排列 if (k == n-1) //終結條件成立時輸出此項排列 { for (int i = 0; i < n; i++) cout << c[i] << " "; cout << endl; } else // 讓c[k]固定不動，求 perm(c[], k+1, n) { for (i=k; i<n; i++){ //讓c[k]~c[n-1]輪流當c[k] char temp=c[k]; c[k]=c[i]; c[i]=temp; //產生a[k+1],…,a[n-1]的所有排列 perm(c,k+1,n); //還原原字元順序 temp=c[k]; c[k]=c[i]; c[i]=temp; } 程式1-3 產生排列

38 產生排列的測試程式 int main() { char a[] = {‘A', ‘B', ‘C', ‘D'};
A B D C A C B D A C D B A D C B A D B C B A C D B A D C B C A D B C D A B D C A B D A C C B A D C B D A C A B D C A D B C D A B C D B A D B C A D B A C D C B A D C A B D A C B D A B C 產生排列的測試程式 int main() { char a[] = {‘A', ‘B', ‘C', ‘D'}; cout << “A B C D 的排列：" << endl; perm(a, 0, 3); system(“pause”); return 0; }

39 遞迴練習：河內塔遊戲 Hanoi Tower：十九世紀在歐洲的一個遊戲。有3根柱子， 及64個大小不同中間有洞的盤子，由上到下由小到大的置於第一根柱子裡。 現在要將這些盤子搬到第三根柱子，一樣由小到大的堆放在第三根柱子裡。 規則： 搬運的過程中，小盤子必須一直保持在大盤子的上面。 可以藉助第二根柱子來完成。

40 遞迴練習：河內塔遊戲 示範程式

41 1.5 演算法的效率分析 什麼是有效率的演算法？電腦學家為此衡量準則提供了客觀的標準—分析演算法的執行時間和記憶體需求。以時間複雜度或空間複雜度來討論演算法的效率 解決相同的問題，演算法所用的時間複雜度和空間複雜度愈少愈好。 時間複雜度(time complexity)：一個程式或演算法所需的執行時間； 空間複雜度(space complexity)：一個程式或演算法所需的記憶體空間。

42 1.5.1 演算法的執行次數 程式1-4 陣列元素加總 int Sum(int data[],int n) { int summation=0; for (int i=0; i<n; i++) summation += data[i]; return summation; } 程式1-4將傳入整數陣列data 中的n個元素 (data[0]~data[n-1])，總加至整數變數summation中傳出。 程式1-5 陣列元素加總並計算所有指令執行的次數 int count = 0; // 全域變數宣告 count++; // 計算宣告 int 指令的執行 int Sum(int data[],int n) { int summation=0; for (int i=0; i<n; i++) { count++; // 計算 for 指令的執行次數 summation += data[i]; count++; // 計算 = 指令的執行次數; } count++; // 計算最後一次 for 指令的執行 count++; // 計算 return 指令的執行 return summation; 在程式1-4中加入一全域變數count，來加總所有指令執行的次數；新的程式將如程式1-5所示。

43 1.5.1 演算法的執行次數(續) 程式1-6 只保留程式1-5 的主體和加總count 的指令。
程式1-6 計算陣列元素加總所有指令執行的次數 count++; int Sum(int data[],int n) { count++; // 計算宣告 int 指令的執行 for (int i=0; i<n; i++) count += 2 count += 2; } 程式1-6 只保留程式1-5 的主體和加總count 的指令。 此程式的執行總次數為2n+4，其中 for 迴圈每執行一次，count會計數兩次；而迴圈共計有n次，所以for迴圈內即執行2n 次。

44 1.5.2 演算法複雜度的表示方法：O、Ω 和Θ 假設有兩個演算法都可解決問題P，其輸入資料量為n；演算法 A 的估算執行次數為 4n2+174，演算法 B 的估算執行次數為 n3+5n+6。(見下圖) 在 n>7 後 演算法 A 比 B 好

45 1.5.2 演算法複雜度的表示方法：O、Ω 和Θ 精確計算演算法的執行步驟或時間的工作過於繁瑣。 電腦處理的是大量的資料。
我們比較關心：資料量大的時候，演算法是否夠好。 精簡的方法分析： 演算法的複雜度：O ，「Big Ｏ」「大Ｏ」 問題的複雜度：Ω 最佳演算法： Θ

46 用大O表示時間複雜度 定義：f (n)=O (g (n)) 若且唯若存在兩個正整數c和n0，當nn0時，f (n)  cg (n)。
f(n)指的是演算法的執行時間（步驟），我們希望能找到g(n)；只要在nn0後，cg(n)一定會大於或等於f(n)，那麼就可以用O(g(n))來表示f(n)。

47 請注意在上圖中，當n  14 (=n0) 之後，cg(n) 一定會大於或等於f(n)（5n2  4n2+174），
所以O(n2)足以代表4n2+174 。

48 範例1-7 4n+12 = O(n)，因為存在c=5，n0=12，使得n12後，4n+12 5n（或c=6，n0=6，使得n6後，4n+12  6n）； 10n+25 = O(n)，因為存在c=12，n0=13，使得n13後，10n+25  12n； 8n2+11n+18 = O(n2)，因為存在c=9，n0=13，使得n13後，8n2+11n+18  9n2； 6×2n+n2 = O(2n)，因為存在c=7，n0=4，使得n4後，6×2n+n2 7×2n；

49 範例1-7 (續) 326 = O(1)，因為存在c=327，n0可任取，使得n n0後，326  327×1；
9n2+n+11  O(n)，因為找不到適當的c和n0，使得nn0後，9n2+11  cn； 100n3 = O(n4)，因為存在c=16，n0=8，使得n8後，100n3 16n4。

50 以大O表示法分辨演算法的優劣 O(1)稱為常數時間，即不論演法的步驟須需要多少指令，只要不像迴圈般重複執行，皆視為常數時間；
O(n)稱為線性時間，取其執行步驟的增加趨勢與n的增加趨勢為線性關係之意； O(n2)為平方時間；依此類推， O(2n)則稱為指數時間。 如此一來，我們會說O(logn)的演算法比O(n)來得有效率，O(n)比O(n2)來得有效率…。

51 O(2n) O(n2) n≤10 ，大O函數值的變化

52 O(n2) 10 ≤ n ≤ 100，大O函數值的變化

53 大O表示函數的優劣順序為： O(1)  O(logn)  O(n)  O(nlogn)  O(n2)  O(n3)  O(2n)

54 用Ω表示問題的難易程度 大O的符號是為了方便討論「演算法的複雜度」而設計引用的； Ω則不然，它是為了方便討論「問題的難易程度」而設計引用的。其定義如下，假設f, g0： 定義：f (n)=Ω (g (n)) 若且唯若 存在兩個正整數c和n0，當nn0時， f (n)cg (n)。

55 範例1-8 (a) 4n+12 =(n)，因為存在c=1，n0=1，使得n1後，4n+12  n； (b) 10n+25 =(n)，因為存在c=10，n0=1，使得n1後，10n+25  10n； (c) 8n2+11n+18 =(n2)，因為存在c=1，n0=1，使得n1後，8n2+11n+18  n2； (d) 6×2n+n2 =(2n)，因為存在c=1，n0=1，使得n1後，6×2n+n2  1×2n；

56 範例1-8 (續) (e)326 =(1)，因為存在c=1，n0可任取，使得nn0後，326  1×1； (f)9n2+n+11 (n3)，因為找不到適當的c和n0，使得nn0後，9n2+11  cn3； (g)100n3 =(n2) =(n) =(1)，因為存在c=1，n0=，使得n1後，100n3  n2 n  1。

57 最佳 (optimal) 演算法 定義：f (n) = θ(g (n)) 若且唯若存在 參個正整數c1、c2和n0，當nn0時，
如果既可找到演算法 A 來解決問題 P，時間複雜度為O(g(n))，且又能証明解決問題 P 的最少代價亦為Ω(g(n))；則欲解決P的時間，至多要O(g(n))，至少為Ω(g(n))；不可能多於O(g(n))，也不可能少於Ω(g(n))（最多或最少都只是g(n)的常數倍），則演算法A是解決問題P的最佳 (optimal) 演算法。 定義：f (n) = θ(g (n)) 若且唯若存在 參個正整數c1、c2和n0，當nn0時， c1g (n)  f (n)  c2g (n)。

58 範例1-9 4n+12 = θ(n)，因為存在c1=1、c2=5，n0=12，使得n12後，1n  4n+12  5n； 8n2+11n+18 = θ(n2)，因為存在c1=1、c2=9，n0=13，使得n13後，1n2  8n2+11n+18  9n2。

59 程式效能分析

60 程式效能之評估法 程式分析(performance analysis) 程式測量(performance measurement)
分析的方式 程式測量(performance measurement) 藉助實驗的方法

61 程式效能 程式的空間複雜度(space complexity) 程式的時間複雜度(time complexity)

62 程式需要的空間 指令空間(instruction space) 資料空間(data space)
常數與簡單變數 複合變數與動態配置的資料 環境堆疊空間(environment stack space) 程式執行時之必要資訊：例如：函數呼叫的參數、區域變數及返回之位址。

63 程式需要的空間 靜態資料 動態資料 指令空間(instruction space) 資料空間(data space)
常數與簡單變數 複合變數 動態資料 環境堆疊空間(environment stack space) 動態配置的資料

64 程式之時間複雜度 執行程式所需要的時間 Tp(n) 兩個更可行的方法
Tp(n) = caADD(n)+csSUB(n)+cmMul(n)+cdDIV(n)+… 所需運算的次數：ADD(n)加法、SUB(n)減法、Mul(n)乘法、DIV(n)除法。 每一指令所需的時間：加法ca、減法cs、乘法cm、除法cd。 兩個更可行的方法 找出關鍵運算，確定關鍵運算所需運算次數 確定程式全部的執行次數。

65 n階乘 的計算 n階乘的計算： n! = n(n-1) (n-2)  … 2 1 int X(int n) { int i,x;
for(i=n;i>0;i--) x=x*i; return x; }

66 迴圈(Loop)程式的複雜度 n階乘的計算 Time complexity int X(int n) { int i,x; x=1;
Space complexity sp(n)=3 int X(int n) { int i,x; x=1; for(i=n;i>0;i--) x=x*i; return x; }

67 n階乘函數 // Compute n! int Factorial(int n) { if (n <= 1) return 1;
else return n * Factorial(n - 1); }

68 else return n * Factorial(n - 1); }
? F(1) int Factorial(int n) {// Compute n! if (n <= 1) return 1; else return n * Factorial(n - 1); } n 2 F(1) ? F(2) n 3 F(2) ? F(3) n 4 F(3) ? F(4) int main(int argc, char *argv[]) { cout << "5! = " << Factorial(5) << endl; system("PAUSE"); return EXIT_SUCCESS; } n 5 F(4) ? F(5) Main F(5) ?

69 else return n * Factorial(n - 1); }
int Factorial(int n) {// Compute n! if (n <= 1) return 1; else return n * Factorial(n - 1); } n 2 F(1) 1 F(2) n 3 F(2) ? F(3) n 4 F(3) ? F(4) int main(int argc, char *argv[]) { cout << "5! = " << Factorial(5) << endl; system("PAUSE"); return EXIT_SUCCESS; } n 5 F(4) ? F(5) Main F(5) ?

70 else return n * Factorial(n - 1); }
int Factorial(int n) {// Compute n! if (n <= 1) return 1; else return n * Factorial(n - 1); } n 3 F(2) 2 F(3) n 4 F(3) ? F(4) int main(int argc, char *argv[]) { cout << "5! = " << Factorial(5) << endl; system("PAUSE"); return EXIT_SUCCESS; } n 5 F(4) ? F(5) Main F(5) ?

71 else return n * Factorial(n - 1); }
int Factorial(int n) {// Compute n! if (n <= 1) return 1; else return n * Factorial(n - 1); } n 4 F(3) 6 F(4) int main(int argc, char *argv[]) { cout << "5! = " << Factorial(5) << endl; system("PAUSE"); return EXIT_SUCCESS; } n 5 F(4) ? F(5) Main F(5) ?

72 else return n * Factorial(n - 1); }
int Factorial(int n) {// Compute n! if (n <= 1) return 1; else return n * Factorial(n - 1); } int main(int argc, char *argv[]) { cout << "5! = " << Factorial(5) << endl; system("PAUSE"); return EXIT_SUCCESS; } n 5 F(4) 24 F(5) Main F(5) ?

73 else return n * Factorial(n - 1); }
int Factorial(int n) {// Compute n! if (n <= 1) return 1; else return n * Factorial(n - 1); } int main(int argc, char *argv[]) { cout << "5! = " << Factorial(5) << endl; system("PAUSE"); return EXIT_SUCCESS; } Main F(5) 120

74 遞迴(Recursive)程式的複雜度 階乘的計算 Time complexity int F(int n)
Space complexity sp(n)= n*2 = 2n int F(int n) { if (n == 1) return 1; return n*F(n-1); }