演算法(Alogrithm)

1、演算法(Alogrithm)李紹群.tw2課本及參考書目n課本(TextBook)n演算法概論n蔡郁彬、胡繼陽、侯玉展著n學貫行銷股份有限公司(EP757)nISBN:978-986-7198-99-0n參考書目(Reference)nIntroduction to Algorithms (Second Edition)nThomas H. Cormen, Charles E. Leiserson,Ronald L. Rivestn演算法：使用C+虛擬碼n蔡宗翰譯n碁峰出版社3評分標準n期中考(30%) n期末考(30%)n平時(20%)n小考n點名n作業(20%)4

2、授課老師n李紹群.twnOffice:承439n分機:81335課程內容n介紹演算法的設計與分析n這不是一門程式設計的課n這門課交你如何寫出一個好的程式n什麼是好的程式n編寫容易(Fast Coding)n沒有錯誤(No Bug)n可重複使用(Reusability)n演算法(Algorithm)6什麼是演算法n演算法是將輸入轉換成結果過程中的一連有順序的計算步驟n在程式設計中所謂的演算法就是如何將CPU使用率及記憶體使用率降到最低7如何通過這門課n高分通過的演算法n上課認真n用心準備考試n低分飛過的演算法n按時上課不缺課n花足夠的時間寫作業及準備考試n明年再來的演

3、算法n不來上課、不做作業、考試靠眼力8是否需要學演算法nCPU越來越快記憶體越來越便宜nCPU不是無限制的快n記憶體不是無限大n現實生活中，大部分的程式都要考量時間及空間的效率n搜尋引擎(search engine)n人類基因序列：3,253,037,807個字母n如何評量演算法n單考慮CPU時間是不公平的n這門課敎你一種方便的評量效能的方式(Big O)n如何成為一個好的程式設計師n在動手寫程式之前分析你的程式9課程內容n演算法簡介n效能分析n排序與搜尋n圖形演算法n演算法的最佳化nNP問題10演算法範例nFibonacci numbern0,1,1,2,3,5,8,13,21,34,55,

4、89,.11Algorithm 1: RecursionnFibonacci numbern0,1,1,2,3,5,8,13,21,34,55,89,.nn=0nn=1nn1, F(n)=F(n-1)+F(n-2)int fab1(int n) if (n=0 | n=1) return 1; else return (fab1(n-1)+fab2(n-2);12Algorithm 2:Loopint fab2(int n) if (n=0 | n=1) return 1; else int tmp1=0, tmp2=1, result; for (int i=2; i=n; i+) resu

5、lt = tmp1 + tmp2; tmp1 = tmp2; tmp2 = result; return result; 13Which One is Better?nAlgorithm 1nAlgorithm 2int fab1(int n) if (n=0 | n=1) return 1; else return (fab1(n-1)+fab2(n-2);int fab2(int n) if (n=0 | n=1) return 1; else int tmp1=0, tmp2=1, result; for (int i=2; i=n; i+) result = tmp1 + tmp2;

6、tmp1 = tmp2; tmp2 = result; return result; 14Analysis of Algorithm 1n指數成長Exponential to nint fab1(int n) if (n=0 | n=1) return 1; else return (fab1(n-1)+fab2(n-2);fib1(100)fib1(99) fib1(98)fib1(98) fib1(97) fib1(97) fib2(96)fib1(97) fib1(96) fib1(97) fib1(96) fib1(97) fib1(96) fib1(96) fib1(95)20=12

7、1=222=423=815Analysis of Algorithm 2 3(n-1)=3n-3 n n線性成長 linear to nint fab2(int n) if (n=0 | n=1) return 1; else int tmp1=0, tmp2=1, result; for (int i=2; i=n; i+) result = tmp1 + tmp2; tmp1 = tmp2; tmp2 = result; return result; 16Which One is Better?nAlgorithm 2 run faster in average and worst casen假使 Fibonacci numb