第一章 資料結構導論 Introduction 版權屬作者所有，非經作者 同意不得用於教學以外用途.

Presentation on theme: "第一章 資料結構導論 Introduction 版權屬作者所有，非經作者 同意不得用於教學以外用途."— Presentation transcript:

1 第一章 資料結構導論 Introduction 版權屬作者所有，非經作者 同意不得用於教學以外用途

2 本章內容 1-1 資料與資訊的意義 1-2 資料結構在學什麼 1-3 演算法的定義與表示法
1-1 資料與資訊的意義 1-2 資料結構在學什麼 1-3 演算法的定義與表示法 流程圖 虛擬碼 1-4 程式的分析 正確達到目的 可維護性高 效率高 記憶體需求低 1-5 迴圈的頻率計數 1-6 Big-O 符號

3 1-1 資料與資訊的意義 ◎ 資料 ( data ) ：用具體符號表示，而能夠被計算機處理的資訊 (information) 。
1-1 資料與資訊的意義 ◎ 資料 ( data ) ：用具體符號表示，而能夠被計算機處理的資訊 (information) 。 ◎ 資訊 ：資料所呈現出來，可經人們分析而理解的訊息。 智慧 知 識 資 訊 資 料 抽象化程度 高 (資料強調符號本身，所以資料較為具體，而資訊較為抽象。 ) ◎ 知識 ( knowledge ) 對現有資訊的學習、歸納或推導而來，是人類（或電腦？）學習與理解資訊所得的結果。 圖1.1 DIKW架構 ◎ 智慧 ( intelligence, wisdom) 則是知識的系統化結果，是對於知識的整體洞察。

4 歷史學家可以從中獲得中國商朝時代的 許多資訊，如政治制度的運作與宗教信 仰的活動等
在近代被發現的「甲骨文」 屬於人類遺產中的重要資料 歷史學家可以從中獲得中國商朝時代的 許多資訊，如政治制度的運作與宗教信 仰的活動等 他們更研究整理了這些資訊，形成一門 獨特的知識，稱為「甲骨學」 通達甲骨學的學者，能洞察人類文化的 本質，就具有相當的智慧了 圖片來源：維基百科

5 1-2 資料結構在學什麼 ◎ 我們將在資料結構這門課中探討計算機系統所儲存以及處理的資料，並且學習如何組織這些資料，以及處理這些資料的方法。
1-2 資料結構在學什麼 ◎ 我們將在資料結構這門課中探討計算機系統所儲存以及處理的資料，並且學習如何組織這些資料，以及處理這些資料的方法。 ◎ 資料結構可以應用在導航系統 各個地點的位置及道路的「圖形資料」都已經被組織安排過了，只要再配合一些方法算出「最短路徑」，就可以幫助駕駛人解決認路或選擇路徑的問題。 ◎ 資料結構可以應用在搜尋引擎 搜尋引擎事先日夜不斷的蒐集網頁資料，依照關鍵字等線索在電腦主機中建構成「索引結構」(index)，等網路使用者下達關鍵字進行搜尋時，就很快的到索引結構中找出網頁的鏈結並回應給使用者。 ◎ 資料結構可以應用在社群網站 社群網站將每一個人視為「圖形結構」上的一個點，兩個人若是朋友則相對的兩個點就會有一條連接線。如果A與B都有共同的朋友C，而且A與B還不是朋友，社群網站就會向A推薦B且向B推薦A。當任一方接受推薦並且獲得另一方確認時，社群網站就牽線成功，在A點與B點之間加上連接線。

6 1-3 演算法的定義與表示法

7 1-3 演算法的定義與表示法 ◎資料結構＋演算法＝程式
1-3 演算法的定義與表示法 ◎資料結構＋演算法＝程式 ◎ 演算法 (algorithm) 的定義：在有限步驟內解決數學問題的程序。 在計算機科學的領域中，演算法泛指 “適合被實作為計算機程式的解題方法” ◎ 演算法通常具有以下五個特性： 一‧輸入 (Input) 二‧明確性 (Definiteness) 三‧正確性 (Correctness)或是 有效性 (Effectiveness) 四‧有限性 (Finiteness) 五‧輸出 (Output)

8 演算法描述如下： 例1.4 歐幾里得演算法 計算兩個自然數的最大公因數 (Greatest Common Divisor, GCD)
歐幾里得(Euclid)是古希臘的數學家(西元前325年—西元前265年) 歐幾里得演算法被公認為是歷史上第一個演算法 在現代的密碼學中，它是在電子商務安全機制中被廣泛使用的「公鑰加密演算法」的重要元件 演算法描述如下： 敘述1. 輸入兩個自然數 A , B 敘述2. A 除以B，餘數為 R 敘述3. 如果 R 為零，則跳至敘述 5 敘述4. A←B，B←R，跳至敘述 2 敘述5. B 即為 GCD

9 例1.4 歐幾里得演算法 計算兩個自然數的最大公因數 (Greatest Common Divisor, GCD)
A B R 敘述1. 輸入兩個自然數 A , B A = 18, B = 12 18 12 敘述2. A 除以B，餘數為 R R = 18 MOD 12 → R =6 敘述3. 如果 R 為零，則跳至敘述 5 R ≠ 0 敘述5. B 即為 GCD (B=6) 敘述2. A 除以B，餘數為 R R = 12 MOD 6 → R = 0 12 6 0 敘述4. A←B，B←R，跳至敘述 2 A = 12 ( A←B ), B = 6 ( B←R ) 敘述3. 如果 R 為零，則跳至敘述 5 R = 0

10 以上敘述符合演算法的特性 一‧輸入 (Input) ：兩個自然數A, B 二‧明確性 (Definiteness) ：以逐步追蹤法 一步一步執行敘 述，不造成混淆 三‧正確性 (Correctness) ：以兩組(A>B及A<B)輸入執行均 得到正確 結果 四‧有限性 (Finiteness) ：R愈來愈小，R終會等於零 五‧輸出 (Output) ：A, B 的最大公因數

11 R2 < B2且B2 = R1代表R2 < R1 R1 > R2 >…> Rn

12 用流程圖來描述這個演算法 「開始」及「結束」通常使用 「膠囊」形狀的符號如與 「平行四邊形」通常是指「輸入」 或「輸出」，如與
用流程圖來描述這個演算法 「開始」及「結束」通常使用 「膠囊」形狀的符號如與 輸入自然數A,B R = A MOD B A ← B B ← R 開 始 是 R = 0 ? B為GCD 結 束 否        「平行四邊形」通常是指「輸入」 或「輸出」，如與 「矩形」則是指「處理」或「運 算」，如與的算術運算式與 指定式。 「菱形」是「決策分支」或 「判斷」，在執行時根據條件 決定走適當的分支，如中， 條件成立時（R=0時）往下走到 ，條件不成立時往右走到。

13 用虛擬碼來描述演算法 演算法：計算兩個自然數的最大公因數 輸入自然數A與B 當 R ( R=A MOD B )不為0 時，重複迴圈
用虛擬碼來描述演算法 演算法：計算兩個自然數的最大公因數 輸入自然數A與B 當 R ( R=A MOD B )不為0 時，重複迴圈 A←B（把B的值給A） B←R（把R的值給B） 迴圈結束 輸出B為結果 演算法結束 輸入自然數A,B R = A MOD B A ← B B ← R 開 始 是 R = 0 ? B為GCD 結 束 否       

14 1-4 程式的分析 一個好的程式，通常必須滿足下列的條件： 一‧正確達到目的：通常以具有代表性的多組輸入來測試驗證
二‧可維護性高：牽涉到編寫程式的方法和風格，以下是幾項檢驗項目：   檢驗項目一：編寫程式是否符合模組化的原則，提供由上而下 (Top-Down)的理解思路？ 檢驗項目二：所有的常數變數及函式 (function) 名稱是否有意義？ 檢驗項目三：所有函式的輸入、輸出及功能是否被明確定義？ 檢驗項目四：是否在適當的地方加上註解？ 檢驗項目五：說明文件是否詳實完備？ 三‧效率高：計算程式的時間複雜度來分析效率並尋求改良之道 四‧記憶體需求低：在不影響效率的情況下，需求愈低愈好

15 可維護性—模組化 汽車的模組化架構圖 應用軟體的模組化架構圖 汽車 外殼 動力系統 電力系統 … 車身 車門 … 引擎 軸承 … 電瓶 …
圖書館管理系統 資料變更模組 資料查詢模組 圖書借還模組 … … 新書 登錄 舊書 刪除 欄位 修正 …

16 程式的效率 程式的執行效率反映在程式執行所花的時間長短。 測量程式的執行效率最直接的方式，就是直接量時間。
在程式的開頭和結尾各記錄一次時間，兩個時間差就是執行的時間。 同樣的程式，經過不同的編譯程式編譯，或在不同的硬體或作業系統上執行，都可能量測到不同的執行時間。 只看程式碼也可以評估效率，我們可以計算程式中所有敘述被執行的總次數，也就是「頻率計數」( frequency count )，並且用頻率計數來比較程式的效率，因為頻率計數愈大，執行的時間也應該愈長。

17 結構化程式的效率三種結構 循序敘述的頻率計數 決策分支敘述的頻率計數 迴圈敘述的頻率計數 Statement 1 Statement 2
檢查點 condition True False statements-1 statements-2 迴圈敘述的頻率計數 符合 不符合 迴圈主體 loop statements 檢查點條件 condition

18 頻率計數的計算 循序敘述的頻率計數 1. Q = m / n ; 2. R = m % n ;
計算循序敘述片段的頻率計數，只要將敘述的行數加總即可。 下列的程式片段，計算整數 m 除以整數 n 的商數以及餘數： 1. Q = m / n ; 2. R = m % n ; 3. printf(“%d  %d = %d … %d”, m, n, Q, R); // cout << m << “  ” << n << “ = “ << Q << “…” << R; 這個程式片段的頻率計數為 3，因為不管m和n的值為何，這3個敘述都會被執行。

19 決策分支敘述的頻率計數 取各個條件分支中總行數的最大值加上比較敘述的次數。下列的程式片段是用來計算整數 m 除以整數 n 的商數以及餘數，但是會先對除數的值加以判斷： 1. if ( n == 0 ) 2. printf(“Error ! Divisor cannot be Zero !”); //cout << “Error ! Divisor cannot be Zero !”; 3. else 4. { Q = m / n ; 5. R = m % n ; 6. printf(“%d  %d = %d … %d”, m, n, Q, R); //cout <<m <<“”<<n << “ = “ << Q << “…” << R; 7. } 頻率計數為 4 ( = )，因為在兩個可能的分支中，最大的區塊有3個敘述（第4行至第6行），加上一個比較 ( if ) 是一定要執行的。

20 迴圈的頻率計數 先根據「迴圈計數器」的範圍算出迴圈重複的次數 再乘上迴圈主體的行數。 下列的程式片段，計算10組整數除法的商數及餘數
1. for ( i = 0; i < 10 ; i++) 2. { Q = m[i] / n[i] ; 3. R = m[i] % n[i] ; 4. printf(“\n%d  %d = %d … %d”, m[i], n[i], Q, R); //cout<<m[i]<<“”<<n[i]<<“=“ << Q << “…” << R; 5. } 迴圈重複10次 ( i 從0~9)，迴圈內有3個敘述，迴圈的主體（第2行到第4行）的頻率計數為30 ( = 10  3 )。 第1行for迴圈的頭會執行11次，前10次造成迴圈主體的重複執行，第11次發現條件不符而離開迴圈。 整個迴圈（迴圈的頭加上迴圈的主體）的頻率計數為 41 ( = )。

21 for迴圈的計數 單層迴圈 1 for ( i = 1 ; i <= n ; i++) 2 result = result + 1 ;
迴圈計數器 i 的範圍是1… n，因此迴圈共重複 n 次 簡單的數學式： 總次數 ＝ = n

22 雙層迴圈、內圈固定次數 2 for ( j = 1 ; j < n ; j++) 3 result = result + 1 ;
1          for ( i = 1 ; i < = n ; i++) 2 for ( j = 1 ; j < n ; j++) result = result + 1 ; 外圈迴圈計數器 i 的範圍是 1… n，內圈迴圈計數器 j 的範圍是 1… n-1， 外圈每執行1圈，內圈就會執行 n-1 圈。而外圈會執行 n 圈，因此第3行敘述共將執行 n (n-1) 次。 數學式： 總次數 ＝ = = n (n-1)

23 雙層迴圈、內圈不固定次數 2 for ( j = i+1 ; j <= n ; j++)
1          for ( i = 1 ; i < = n ; i++) 2 for ( j = i+1 ; j <= n ; j++) result = result + 1 ; 由於內圈迴圈計數器 j 的範圍，是隨著外圈迴圈計數器 i 的範圍改變的，因此我們針對迴圈計數器 i 的變化來分析：

24 總次數 ＝ (n-1) + (n-2) + … + 1 = n * ( n-1 ) / 2
i 的值 j 的範圍 第3行執行次數 1 2 …… n n-1 2 3 …… n n-2 3 4 …… n n-3 … n …… n n n+1 …… n 總次數 ＝ (n-1) + (n-2) + … + 1 = n * ( n-1 ) / 2 數學式： 總次數 ＝ = = = n2 – =

25 計算n階乘 ( n! ) 的函式： 計算每一行敘述被執行的次數： { int result, i ; 1 result = 1 ;
int factor( int n) { int result, i ; 1               result = 1 ; 2               i = 1 ; 3               while ( i < = n ) 4               { 5                 result = result * i ; 6                  i = i + 1 ; 7                } 8                return result; } 計算每一行敘述被執行的次數： 行號 n>0 時 n <= 0 時 1 2 3 n+1 5 n 6 8 總次數 3n+4 4 多1次為最後一次比較條件不成立 如果 n>0，頻率計數為 3n+4次， 如果 n <= 0 ，頻率計數為 4次

26 1-5 Big-O符號 Big-O符號的數學定義為：若且唯若 f(n) = O(g(n)) 則存在大於 0 的常數 c 和 n0，使得對所有的 n 值，當n ≧ n0 時，f(n) ≦ c * g(n) 均成立。 用數學式表示為： f(n) = O(g(n))   c, n0>0   n≧ n0 , f (n) ≦ c * g(n) 用口語解釋為：f(n) 取Big-O符號為O( g(n))，當 n 夠大的時候，g(n)相當於是f(n)的上限  用圖示可表達為： c*g(n) f(n) n n0

27 5n2 + 6n + 9 ＝ O(n2) → f(n) = 5n2 + 6n + 9, g(n) = n2 → f 函數取 Big-O 符號為 g 函數 → 5n2 + 6n + 9 取 Big-O 符號為 O(n2) 3n lg n + 9n + 10 = O(n lg n) ，因為 n lg n 的次數比 n 大，取最高次項而不計係數時，自然取到 n lg n (lg n = log2n) 9n2 + 6n lg n + 9 = O(n2) ，因為 n2 的次數最大，取最高次項而不計係數時，自然取到 n2 19n3 + 9n2 + 6n + 9 = O(n3) ，因為 n3 的次數最大，取最高次項而不計係數時，自然取到 n3

28 常見的時間複雜度等級有： O(1) ：常數級 ( constant ) O(lg n) ：對數級 ( logarithmic )
O(n) ：線性級 ( linear ) O(n lg n) ：對數─線性級 ( log linear ) O(n2) ：平方級 ( quadratic ) O(n3) ：立方級 ( cubic ) O(2n) ：指數級 ( exponential ) O(n!) ：階乘級 ( factorial ) 成長速度順序是： O(1) ＜ O(lg n) ＜ O(n) ＜ O(n lg n) ＜ O(n2) ＜ O(n3) ＜ O(2n) < O(n!) 解決同樣問題的三個程式， 時間複雜度分別是 O(n2)、O(n lg n)、O(n3)，時間複雜度為O(n lg n)的程式較有效率。 這就是概略分級的意義，使我們能簡單比較程式的效率。

29 n g(n) 2 10 50 100 500 1千 1萬 1百萬 lg n 1 3.3 5.6 6.6 9 13.3 20 1000 10000 106 n lg n 33 280 660 4500 1.3×105 2×107 n2 4 2500 250000 108 1012 n3 8 125000 1.25×108 109 1018 2n 1024 1015 1030 10150 10300 103000 n! 3×1064 9×10157 101134 4×102567 3× 太大 O(1) < O(lg n) < O(n) < O(n lg n) < O(n2) < O(n3) < O(2n) < O(n!)

30 ( X軸代表n值的成長，Y軸代表g(n)值的成長 )
25 210 215 220 225 230