算法设计与分析学习心得

020906 郭晓敏   2002．1．14 

算法是计算机科学的核心，是程序设计的精髓。算法设计与分析作为我们计算机系研究生必修课程之一有其必要性。以前在本科阶段，学校开设了算法选修课，不过当时我没有选修这门课，没有认识到算法知识的重要性。现今，在硕士研究生学习阶段，通过一个学期的算法学习，收获不少，感觉思维豁然开朗，在原有知识层次上有了一个跃升。该门课提出了解决问题的许多新思路和新方法，可以激发我们的发散思维和创造性思维，让我认识到高效的算法对于高效程序设计的重要性，学会对算法的时间复杂度分析。

在学习新知识的新鲜感逐渐减弱后，我越来越感到算法学习的难度。每次算法课都要接受大量的知识，而知识具有一定的深度，课堂上往往不能完全消化，每次课后都要花时间细细看笔记，思考理解每一个细节。遇到不懂的问题，便和同学交流探讨，或是向老师询问。除了力求课堂笔记的掌握外，每次作业也都认真对待，不仅要求做出正确答案，也要寻找更好的算法。印象最深的是那次编程实现KMP,Monte Carlo和Las Vegas算法的作业。起初，我对题意不甚理解，不知从何下手，通过自己对相关知识的回顾以及和同学的交流，我渐渐明晰了程序功能，编出了程序，加深了对知识的理解。在这一过程中，我发现自己对一些库函数还不熟悉，程序设计能力有待进一步提高。

都说“苦学其乐”，在知难而上的学习过程中，我也领悟到了学习的乐趣。算法知识本身也是渗透着乐趣的。而且，当我消化吸收了新知识，当我经过思考搞明白不懂的问题，或是终于解出一道难题，心中总是会充溢着快感。

随着学习的深入，我由零碎的知识逐步了解到算法知识的整体框架和各部分的相关性，慢慢理出了条理，尤其是最后阶段的复习，更是让我对算法有了一个总体上的认识和把握。算法设计与分析这门课涵盖面广，但也是有系统性的，可以分为五部分。要分析一个算法的执行，就必须有某个计算机模型。算法课从讲述随机存取机器（RAM）、随机存取程序存储机器（RASP）和图灵机等计算机模型开始，逐步深入下去，引入了分治法、动态规划、集合运算、随机算法以及NP_C问题和近似算法。内容不少，还是有脉络可循的。

图灵机等计算模型简单得足以获得分析结果，同时又能正确反映现实计算机的特点，是理解算法知识的基础和入门。接着讲述了算法分析的数学基础知识，涉及组合数学，如用生成函数法求解非线性递归方程。

还介绍了有效算法的设计，评价算法应从正确性、健壮性、简单性、高效性、最优性等五个方面考虑。介绍了分治法和动态规划法。

分治法把一个规模为n的问题分解为若干个规模较小的子问题，这些子问题相互独立，且与原问题同类，首先求解出子问题的解，然后把这些子问题的解组合成原问题的解。分治法很自然地要用到递归。分治法符合人类思维习惯，简单高效。子问题规模小，自然比规模较大的原问题容易求解，采用递归，子问题的解求出了，原问题的解也就容易得出。分治法对大规模的复杂问题很有效。在找出n个元素中的最大元和最小元、矩阵乘法、求第k个最小（大）元、寻找最近点对等问题中的应用可以很明显地看到分治法的优势所在。

使用分治法时，所划分的子问题的规模应当尽量接近，这时，递归技术是有用的。但是，如果把一个规模大小为n的问题明显地分为n个大小为n-1的子问题，而仍采用递归，则算法可能有幂的增长，这时可采用与分治法相类似的动态规划法。

动态规划法把问题层层分解为规模逐渐缩小的子问题，与分治法不同的是，这些子问题有很多都是重复的。计算从小到大的子问题进行，把答案保存下来，以后再碰到同样的问题就不用再计算。分治法导出的是递归，而动态规划法导出的是递推（自下而上）。若问题具有高度的重复性和最优子结构性质，则可采用动态规划法，免去了很多重复计算，减小了时间复杂性。其在最优二分搜索树、最长公共子序列（LCS）问题上有着成功的应用。但在有大量子问题无须求解时，用备忘录方法对算法改进，可获得较好的时间复杂性。

集合运算是算法的重要组成部分。一个问题可用像集合这样的数学对象来描述，而该问题的算法可以用这些基本对象的基本运算来表出。可以通过集合运算来寻求好的算法设计。这一部分主要讲述了UNION_FIND问题及其应用和推广。可以看到，该问题有广泛的应用，能以好的时间复杂性提供灵活有效的解法。而平摊分析的聚集方法、会计方法及势能方法给出了求解时间复杂性的易理解的有效途径，方便评价算法。这些都是我们在实践中可以吸收采纳的。

有不少问题，目前只有效率很差的确定性算法，但采用随机算法可快速获得相当可信的结果。它往往比当前已知的确定性算法的时间复杂性要好，而且避免了去构造最坏情况的例子，在理解与实现上都是极为简单的。对于设计高效的算法大有裨益。随机算法拓展了我们解决问题的思维空间。

另外，学习算法分析与设计，不能不了解NP_C理论及近似算法。这部分知识的学习，不仅看懂笔记，我还参阅了教材，尽可能掌握，当然还有需要进一步理解的地方。仅仅理解笔记是不够的，要会应用才是主要的。在证明两个问题存在≤p关系时所采用的转换方法都大可借鉴，我们可能一下子想不到。比如3CNF_SAT≤PCLIQUE的证明，将一个3CNF_SAT是否可满足转换为一个无向图G中是否有一个K_团的问题。限制法是证明NP_C问题的有效方法。再往后，装箱问题，背包问题以及PTAS和FPTAS的介绍更是开拓了我们的视野。

以上便是我对算法分析与设计这门课的总体印象和了解。总之，算法分析与设计这门课的学习提供了许多新的解题思路和有效算法，为我洞开了一片以前所未了解的世界，令我开拓思维空间，提高分析和解决问题的能力，必然会对今后的学习和研究起到积极的作用。

   2002．1．14