資訊工程研究所申設簡報InformationEngineeringResearchInstitute.ppt
《資訊工程研究所申設簡報InformationEngineeringResearchInstitute.ppt》由会员分享,可在线阅读,更多相关《資訊工程研究所申設簡報InformationEngineeringResearchInstitute.ppt(33页珍藏版)》请在三一文库上搜索。
1、資電學院 計算機概論 F7810,第四章 演算法導論,陳邦治編著 旗標出版社,2,本章重點,程式製作的過程為程式設計師會先根據使用者的需求(user demand)來設計演算法,然後再挑選一個適合的程式語言,根據程式語言的語法及設計好的演算法來撰寫(coding)程式 程式設計與演算法之間的關係十分密切 本章將介紹演算法的相關知識,3,大綱,演算法基本觀念 演算法分析 設計程式的方法 發展程式的方法,3,3,4,演算法基本觀念,演算法(algorithm)是指是有限數目指令的集合,利用這群指令撰寫的程式可以完成某個特定的工作,5,演算法基本條件,演算法有五項基本的條件,必須五項條件都滿足才符合
2、演算法的要求,五項條件如下 輸入(input)條件 0個或0個以上的輸入,也就是說演算法允許沒有輸出 輸出(output)條件 演算法要求至少應有1個輸出 明確性(definiteness)條件 演算法要求定義必須明確不可模擬兩可(ambiguous)。 有限性(finiteness) 條件 演算法要求不可存在無窮迴路(infinite loop),也就是說必須在有限步驟內完作。 有效性(effectiveness)條件 演算法執行的結果應是正確的,6,演算法基本條件(cont.),任何一種計算方法必須滿足以上五項條件才符合演算法的要求。如果某一種計算方法執行的結果是錯誤的,就算該計算方法滿足
3、輸入、輸出、明確性及有限性四項條件而且或許執行的速度也很快,但是一個錯誤的計算方法就不能算是演算法,7,實例:一個演算法的例子,演算法,程式段,8,演算法分析,由於程式是根據演算法撰寫而成,因此程式與其對應的演算法關係必定非常密切 若演算法設計得宜,則程式的執行效率及記憶體空間的使用情形都會有處於較理想的狀況 分析或評估程式效能的方法可分別就程式執行所需的時間(time)與程式執行所需的記憶體空間(space)二方面來著手,9,影響程式執行時間的因素,輸入資料量的數量 所採用的演算法之時間複雜度(Time Complexity) 編譯器的優劣 計算機的執行速度,10,漸進符號(asymptot
4、ic symbols),漸進符號常被用來分析演算法的時間複雜度,雖然此法無法精確地表達演算法實際執行次數,但因可利用簡單的近似值表達演算法所需的時間複雜度,因此被廣泛採用,11,漸進符號種類 (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)便代表函數f(n)的漸進上限,12,漸進
5、符號種類 (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)函數的下限,13,漸進符號種類 (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) cg(n) (唸作th
6、eta)是利用上限及下限來逼近一個函數。若f(n)(g(n),則g(n)可同時代表f(n)的上限及下限,14,常見的時間複雜度,假設 n 表示要處理的資料量,請注意: 0(1)0(log2 n)0(n)0(nlog n)0(n2)0(n3) 0(2n) 0(n!),15,範例 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),16,範例2,寫出下列f(n)的時間複雜度: f(n)2n23n500 解:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 工程研究所 申設簡報 InformationEngineeringResearchInstitute
链接地址:https://www.31doc.com/p-2766924.html