做了不少届的考题，分享一些心得，不过这是我前一段时间整理的，资料可能有点旧。 ----------------------------------------------------------------------------- 要解决一个演算法设计问题，首先要想出要使用哪种策略来解决， 但是演算法设计策略很多，看到题目往往不知道要用哪个。不过研 究所考题有一些性质，首先是考题是老师认为在时间内可以写完的 ，所以不会出非常复杂的演算法，像是要先证明一大堆的性质，最 後才得以解决的。再来是考题为了增加难度，有时候会限制时间或 是空间复杂度。 下面的方法只是一个大概的方法，没办法适用於所有的题目，而且 有时候必须要混用演算法技巧才能解题，不过还是希望能有一些帮 助。 首先把题目归类为图论和非图论，因为图论的演算法大多需要藉由 性质来解决，比较没有办法分析。 这些都是典型的图论题目 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