資料結構與演算法 第一章　基本概念 徐熊健 資料結構與演算法 徐熊健.

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

1 資料結構與演算法 第一章　基本概念 徐熊健 資料結構與演算法 徐熊健

2 目錄 1.1 資料結構、演算法 1.2 資料結構與演算法 1.3 簡單的資料結構 1.4 演算法初探 1.5 演算法的效率分析
1.1　資料結構、演算法 1.2　資料結構與演算法 1.3　簡單的資料結構 1.4　演算法初探 1.5　演算法的效率分析 資料結構與演算法 徐熊健

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

4 1.2　資料結構與演算法 電腦處理的對象稱為「資料」(data)，泛指所有輸入至電腦中，即將、正在或已經被電腦程式處理的符號總稱；包括了數值(numerical) 資料、字串 (string) 資料等等，乃至於目前多媒體 (multimedia) 軟體所處理的影像、聲音、視訊等多媒體資料。 當這些資料集合在一起時，會因處理需求的不同而存在一種或多種彼此之間的特定關係，這些資料之間的邏輯關係，就稱為結構 (structure)。研究資料的邏輯關係，探討這些邏輯關係在電腦中的表現 (representation) 和處理 (manipulation) 方式，即為「資料結構」。 資料結構與演算法 徐熊健

5 1.3 簡單的資料結構 生活中常見的資料相互關係： (1)校園中有一群人； (2)每個中華民國國民皆有唯一的身分證字號；
1.3　簡單的資料結構 生活中常見的資料相互關係： (1)校園中有一群人； (2)每個中華民國國民皆有唯一的身分證字號；  (3) 每位同學在班上皆有唯一的座號、在學校皆有唯一的學號； (4)在大學中的科系有系別、年級別、甚至於班別； (5) 排隊的時候，我們可能只關心排在前一位的是誰？有時可能還在意排在自己前面的共有多少人？ (6)外國旅行時，各景點間是否有班機直飛？ (7)上網尋找資料，網頁間的鏈結，將網頁連結成複雜的全球性的網絡(world-wide web)。 資料結構與演算法 徐熊健

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

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

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

9 演算法1-1 挑選排序法： 輸入：data[0], data[1], data[2], …, data[n-1]，共 n 筆整數資料
若i<j，則data[i]data[j]，1i,jn for (i=0; i<n; i++) { data[j] = 挑出data[i]至data[n-1]中最小者 swap(data[i], data[j]) // 將data[i] 和 data[j] 對調 } 資料結構與演算法 徐熊健

10 程式1-1 挑選排序法： void SelectionSort(int data[], int n) { int i, j;
int min, temp; for (i=0; i<n; i++) { min = i; for (j=i+1; j<n; j++) if (data[j]<data[min]) min = j; temp = data[i]; data[i] = data[min]; data[min] = temp; } 資料結構與演算法 徐熊健

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

12 1.4.2 遞迴演算法 SS(int data[],int n) void SS(int data[],int n) { }
直接遞迴 (direct recursion)：當程序執行完成前呼叫了自己這個程序。 間接遞迴 (indirect recursion) ：在程序執行完成前呼叫了其它會再度引用到自己的程序。 在設計遞迴程式時，切記終結條件 (termination condition) 的設立，否則易造形成無窮迴圈 。 … SS(int data[],int n) void SS(int data[],int n) { } 程序呼叫時流程的轉換 資料結構與演算法 徐熊健

13 程式1-2 計算階乘 int X(int n) { if (n == 1) return 1; return n*X(n-1); }
階乘的計算即可用遞迴的概念詮釋，請看： n! = n(n-1)! 於是可以寫一個計算階乘的程序 X(int n)， 它接受傳入的整數 n，傳回 n*X(n-1) int X(int n) { if (n == 1) return 1; return n*X(n-1); } 資料結構與演算法 徐熊健

14 程式1-3 產生排列 void perm (char c[], int k, int n)
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 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; perm(c,k+1,n); //產生a[k+1],…,a[n-1]的所有排列 temp=c[k]; c[k]=c[i]; c[i]=temp; //還原原字元順序 程式1-3 產生排列 資料結構與演算法 徐熊健

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

16 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所示。 資料結構與演算法 徐熊健

17 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 次。 資料結構與演算法 徐熊健

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

19 用大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)。 資料結構與演算法 徐熊健

20 請注意在上圖中，當n  14 (=n0) 之後，cg(n) 一定會大於或等於f(n)（5n2  4n2+174），
所以O(n2)足以代表4n2+174 。 資料結構與演算法 徐熊健

21 範例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=11，n0=13，使得n13後，10n+25  11n； 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； 資料結構與演算法 徐熊健

22 範例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。 資料結構與演算法 徐熊健

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

24 O(1)  O(logn)  O(n)  O(nlogn)  O(n2)  O(n3)  O(2n)。
資料結構與演算法 徐熊健

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

26 (a) 4n+12 = (n)，因為存在c=1，n0=1，使得n1後，4n+12  n；
範例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； 資料結構與演算法 徐熊健

27 (e)326 = (1)，因為存在c=1，n0可任取，使得nn0後，326  1×1；
範例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。 資料結構與演算法 徐熊健

28 最佳 (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)。 資料結構與演算法 徐熊健

29 4n+12 = Ω(n)，因為存在c1=1、c2=5，n0=12，使得n12後，1n  4n+12  5n；
範例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。 資料結構與演算法 徐熊健