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

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

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

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

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

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

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

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

演算法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] 對調 } 資料結構與演算法 徐熊健

程式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; } 資料結構與演算法 徐熊健

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

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) { } 程序呼叫時流程的轉換 資料結構與演算法 徐熊健

程式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); } 資料結構與演算法 徐熊健

程式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 產生排列 資料結構與演算法 徐熊健

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

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

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

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

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

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

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

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

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

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

用Ω表示問題的難易程度 定義：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)。 資料結構與演算法 徐熊健

(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； 資料結構與演算法 徐熊健

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

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

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