做了不少屆的考題，分享一些心得，不過這是我前一段時間整理的，資料可能有點舊。
-----------------------------------------------------------------------------
要解決一個演算法設計問題，首先要想出要使用哪種策略來解決，
但是演算法設計策略很多，看到題目往往不知道要用哪個。不過研
究所考題有一些性質，首先是考題是老師認為在時間內可以寫完的
，所以不會出非常複雜的演算法，像是要先證明一大堆的性質，最
後才得以解決的。再來是考題為了增加難度，有時候會限制時間或
是空間複雜度。
下面的方法只是一個大概的方法，沒辦法適用於所有的題目，而且
有時候必須要混用演算法技巧才能解題，不過還是希望能有一些幫
助。
首先把題目歸類為圖論和非圖論，因為圖論的演算法大多需要藉由
性質來解決，比較沒有辦法分析。
這些都是典型的圖論題目
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