《資訊工程研究所申設簡報InationEngineeringResearchInstitute上课讲义》由会员分享，可在线阅读，更多相关《資訊工程研究所申設簡報InationEngineeringResearchInstitute上课讲义（33页珍藏版）》请在金锄头文库上搜索。
1、資電學院計算機概論F7810,第四章 演算法導論,陳邦治編著 旗標出版社,本章重點,程式製作的過程為程式設計師會先根據使用者的需求(user demand)來設計演算法，然後再挑選一個適合的程式語言，根據程式語言的語法及設計好的演算法來撰寫(coding)程式 程式設計與演算法之間的關係十分密切 本章將介紹演算法的相關知識,大綱,演算法基本觀念 演算法分析 設計程式的方法 發展程式的方法,3,3,演算法基本觀念,演算法(algorithm)是指是有限數目指令的集合，利用這群指令撰寫的程式可以完成某個特定的工作,演算法基本條件(cont.),任何一種計算方法必須滿足以上五項條件才符合演算法的要求
2、。如果某一種計算方法執行的結果是錯誤的，就算該計算方法滿足輸入、輸出、明確性及有限性四項條件而且或許執行的速度也很快，但是一個錯誤的計算方法就不能算是演算法,實例：一個演算法的例子,演算法,程式段,演算法分析,由於程式是根據演算法撰寫而成，因此程式與其對應的演算法關係必定非常密切 若演算法設計得宜，則程式的執行效率及記憶體空間的使用情形都會有處於較理想的狀況 分析或評估程式效能的方法可分別就程式執行所需的時間(time)與程式執行所需的記憶體空間(space)二方面來著手,影響程式執行時間的因素,輸入資料量的數量 所採用的演算法之時間複雜度(Time Complexity) 編譯器的優劣 計算
3、機的執行速度,漸進符號(asymptotic symbols),漸進符號常被用來分析演算法的時間複雜度，雖然此法無法精確地表達演算法實際執行次數，但因可利用簡單的近似值表達演算法所需的時間複雜度，因此被廣泛採用,漸進符號種類 (1/3),：f(n)(g(n) if and only if there exist 2 positive constants N and c，such that for every n N，f(n) cg(n)。 O(唸作big-oh)代表函數的漸進上限，若f(n)(g(n)，則O(n2)便代表函數f(n)的漸進上限，例如f(n)=3n2+4n+5，則O(n2)便代表
4、函數f(n)的漸進上限,漸進符號種類 (2/3),：f(n)(g(n) if and only if there exist 2 positive constants N and c，such that for every n N，f(n) cg(n)。 (唸作omega)用來估算函數的下限值，若f(n) (g(n)，則g(n)便可視為是f(n)函數的下限,漸進符號種類 (3/3),：f(n)(g(n) if and only if there exist 3 positive constants b ， c and N，such that for every n N， bg(n) f(n)
5、cg(n) (唸作theta)是利用上限及下限來逼近一個函數。若f(n)(g(n)，則g(n)可同時代表f(n)的上限及下限,常見的時間複雜度,假設 n 表示要處理的資料量,請注意： 0(1)0(log2 n)0(n)0(nlog n)0(n2)0(n3) 0(2n) 0(n!),範例 1,寫出下列f(n)的時間複雜度： (1) 5log n+100 (2)8n3-15 (3) 20n2+400 (4)20n3+30n2+40nlogn+50n 解： (1) (log n) (2) (n3) (3) (n2) (4) (n3),範例2,寫出下列f(n)的時間複雜度： f(n)2n23n500
6、解：O(n2),程式段中使用到的P、Q及R滿足P+Q+R=500,範例3,以下程式段中敘述X執行的次數及程式段的時間複雜度各為何？,解： (1) 執行的次數為n次，時間複雜度為O(n) (2) 執行的次數為(nm)次，時間複雜度為O(nm),範例4,試決定下列程式中敘述X的執行次數及程式段的時間複雜度,解：(1) 執行次數：(n+1)n/2 次 (2)時間複雜度：O(n2),範例 5,試決定下列程式中敘述X的執行次數及程式段的時間複雜度,解：(1) 執行次數： (1+n)n/2次 (2) 時間複雜度：O(n2),程式產生的過程,程式產生的過程一般可分為五個階段 需求(requirement)階
7、段 設計(design)階段 分析(analysis)階段 再修飾與編碼(refinement and coding)階段 驗證(verification)階段,五大階段工作,需求階段是根據程式的要求定義出所有可能的輸入及輸出狀況 設計階段是根據需求設計出相對應的演算法 分析階段是嘗試設計出二種以上不同的演算法，再由不同的演算法中決定何者最佳 再修飾與編碼階段是選擇適當的程式語言開發工具對最佳演算法編碼並撰寫出對應的程式 驗證階段是對撰寫出的程式執行證明(proving)、測試(testing)及除錯(debugging)三項工作,常用的程式設計方法,常用的程式設計方法 遞迴法(recursi
8、ve method) 貪婪法(greedy method) 個別擊破法(divide and conquer) 動態程式法(dynamic programming),遞迴法(recursive method),允許副程式直接或間接呼叫本身便稱之為遞迴法 目前常用的程式語言開發工具均提供遞迴功能 如PASCAL、C、C+、Java及Visual Basic等,遞迴法 vs. 非遞迴法 範例1,計算s=1+2+n，其中n1且n為整數,遞迴法較易瞭解，但執行效率較差,遞迴法 vs. 非遞迴法 範例2,計算n!=12n，其中n1且n為整數,遞迴法 vs. 非遞迴法 範例3,計算二整數A及B的最大公因數
9、,貪婪法(greedy method),貪婪法的原則是求出現階段的最佳選擇。將求解的過程細分成一系列的子步驟，每個子步驟所做的選擇都是目前最佳的，而且每個子步驟的選擇在往後皆不得被變更 例如Dijkstra 的單一起點最短路徑演算法，Prime 的最小生成樹演算法和無失真編碼的霍夫曼演算法，都是採用貪婪法,個別擊破法(divide and conquer),將一個問題分解成數個較小的問題，若某些小問題可繼續再被細分，便再將小問題往下再細分成更小的問題，依此類推直到問題獲得解答為止。最後將分解後問題的解答合併成分解前問題的解答，依此類推直到獲得原始問題的解答為止 常見的個別擊破法演算法的範例有快
10、速排序法、二元樹追蹤、圖形的深度優先搜尋及廣度優先搜尋等方法,動態程式法(dynamic programming),動態程式法除了考慮目前的狀況外，還必須考量其他階段的情況後才能做出最佳選擇 例如0/1背包問題 ( 0/1 Knapsack)便可利用動態程式法來解決,發展程式的方法,當程式設計師具備演算法的知識後便可問始設計及發展程式 發展程式常見的方法有 由上而下設計法(top down design) 由下而上設計法(bottom up design),由上而下設計法,由上而下的設計法的主要精神為:先確定最高層的功能，然後產生一層層較低階層的模組與元件 由上而下的設計法是指從事程式設計的過
11、程中，依照程式的邏輯特性將程式細分成幾個較小的問題，再將這些較小的問題同樣依照程式的邏輯特性再往下細分成更小的問題，依此類推直到很容易撰寫程式的單元時為止 優點 程式可分工由多人共同撰寫、因程式已切割為小單元因此較容易除錯及容易維護 缺點 程式段較長且執行時間較久,由上而下設計法範例,以學生資料處理系統為例 依照學生資料處理系統的邏輯特性將問題切割成處理基本資料及成績資料二個較小的問題 再將處理成績資料同樣依照邏輯特性再往下細分成處理操行成績及學業成績二種 程式設計師便可依此設計原則所得之結果來設計程式,由下而上的設計法,由下而上的設計法是指由問題中最容易編寫程式的單元開始設計程式，然後逐級往上層組合成較完整的程式 同樣以學生資料處理系統為例，先設計完成操行成績及學業成績二個最下層(第三層)的程式後，將此二個程式合併成成績資料程式。然後再設計完成第二層基本資料程式，最後合併第二層的基本資料及成績資料二個程式成為最上層的學生資料處理系統,
