做了不少屆的考題，分享一些心得，不過這是我前一段時間整理的，資料可能有點舊。 ----------------------------------------------------------------------------- 要解決一個演算法設計問題，首先要想出要使用哪種策略來解決， 但是演算法設計策略很多，看到題目往往不知道要用哪個。不過研 究所考題有一些性質，首先是考題是老師認為在時間內可以寫完的 ，所以不會出非常複雜的演算法，像是要先證明一大堆的性質，最 後才得以解決的。再來是考題為了增加難度，有時候會限制時間或 是空間複雜度。 下面的方法只是一個大概的方法，沒辦法適用於所有的題目，而且 有時候必須要混用演算法技巧才能解題，不過還是希望能有一些幫 助。 首先把題目歸類為圖論和非圖論，因為圖論的演算法大多需要藉由 性質來解決，比較沒有辦法分析。 這些都是典型的圖論題目 http://www.cs.ccu.edu.tw/recruit/MasterExam/93_CI.pdf 中正資工93第17題 http://www.lib.nthu.edu.tw/library/department/ref/exam/eecs/cs/95/952601.pdf 清大資工95第15題 http://www.lib.nthu.edu.tw/library/department/ref/exam/94/eecs/942501.pdf 清大資工94第13題 http://www.lib.nctu.edu.tw/n_exam/exam96/cslz/cslz1001.pdf 交大資工96第6題 http://140.115.130.224:8080/~arhui/cexamn/exam/EC02_96_01.pdf 中央資工96第5題 http://140.115.130.224:8080/~arhui/cexamn/exam/EC02_95_01.pdf 中央資工95第7題 如果是非圖論的，可以按照題目類型分成兩類： 第一類是最佳化型的，像是求最大、最長、最小、最短之類的，而 這類型題目可以嘗試的方向就是動態規劃和貪婪演算法。這兩個方 法之中，最好先嘗試動態規劃，因為貪婪演算法需要花時間去證明 性質來保證演算法的最佳性，但是動態規劃只要狀態轉移方程沒問 題，演算法的正確性就可以容易地被保證。 而且動態規劃需要先找到遞迴關係，如果正確的解法是貪婪演算法 ，那找遞回關係也可以幫忙想出貪婪演算法的解法。 （動態規劃和貪婪演算法可以解大部分最佳化問題，但不是全部） http://www.lib.ntu.edu.tw/exam/graduate/94/459.pdf 台大資工94第5題 暨南資工93第1題 第二類是非最佳化型的，在這一類中可依照題目要求的時間複雜度 來作分類。 第一子類是要求時間複雜度有 lg n 的，像是O( n lg n )和O( n^2 lg n )。 從這點下去思考，哪些演算法會產生 lg n ，大概就是排序、二分 搜尋、二元樹、堆積和D & C，其中D & C要最後再嘗試，因為D & C 的方法比較難想出來。 http://www.lib.ntu.edu.tw/exam/graduate/92/92449.pdf 台大資工92第6題 http://140.115.130.224:8080/~arhui/cexamn/exam/EC02_97_01.pdf 中央資工97第五題 http://www.cs.ccu.edu.tw/recruit/MasterExam/95software.pdf 中正資工95第11題 第二子類是時間複雜度是n的非整數次方，這種問題多半是D & C， 因為D & C之後算出時間複雜度的遞迴關係式，套用Master Theorem 所產生非整數次方。 第三子類是線性複雜度，能夠維持線性的複雜度的演算法也不多， 像是字串比對、類似找中位數的prune & search的技巧等，都是可 以嘗試的方向。 http://www.cs.ccu.edu.tw/recruit/MasterExam/95software.pdf 中正資工95第12題 剩下的複雜度，或是只限制小於某個複雜度，甚至是根本沒限制複 雜度的就很麻煩，只能憑真本事了。 http://140.115.130.224:8080/~arhui/cexamn/exam/EC02_93_01.pdf 中央資工93第七題 成大資工95第8題 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.119.162.51