做了不少屆的考題，分享一些心得，不過這是我前一段時間整理的，資料可能有點舊。
-----------------------------------------------------------------------------
要解決一個演算法設計問題，首先要想出要使用哪種策略來解決，

但是演算法設計策略很多，看到題目往往不知道要用哪個。不過研

究所考題有一些性質，首先是考題是老師認為在時間內可以寫完的

，所以不會出非常複雜的演算法，像是要先證明一大堆的性質，最

後才得以解決的。再來是考題為了增加難度，有時候會限制時間或

是空間複雜度。


下面的方法只是一個大概的方法，沒辦法適用於所有的題目，而且

有時候必須要混用演算法技巧才能解題，不過還是希望能有一些幫

助。


首先把題目歸類為圖論和非圖論，因為圖論的演算法大多需要藉由

性質來解決，比較沒有辦法分析。

這些都是典型的圖論題目
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