概述
在数学的王国里,质数(也即素数)是数这个范围内一枚闪闪发光的重要宝石,很多公式和定理都与素数有关。这样,如何判断一个数是否是素数也是一个重要的问题,只不过这个问题的解法相当显而易见,那么我们的目光就要更多的放在对于判断素数的算法的性能的优化上了(更多的是时间复杂度)。
在数学的王国里,质数(也即素数)是数这个范围内一枚闪闪发光的重要宝石,很多公式和定理都与素数有关。这样,如何判断一个数是否是素数也是一个重要的问题,只不过这个问题的解法相当显而易见,那么我们的目光就要更多的放在对于判断素数的算法的性能的优化上了(更多的是时间复杂度)。
递推算法作为基础算法之一,递推的思想不难理解,难点在于多变的递推公式以及找寻递推关系时蕴含的数学的思维。由于递推算法的关键问题是得到递推关系,这种关系是一种高效的数学模型(ACM-ICPC基本算法中是这么说的),而且又灵活多变,为递推算法题目的解决带来了不少困难。所以,我认为有必要开专题对常见递推思路进行列举讲解,顺带着讲解一下递推算法的基础知识。
正如百度百科所说,并查集是一种树形的数据结构,并且用于处理一些不相交集合的合并及查询问题。一般地来说,并查集由两个部分组成,一个是查找要操作的两个集合是否属于同一个,另一个则是进行这两个集合合并的过程。
在我看来,每种算法都由两个部分组成,一部分是思想,另外一部分就是实现能力,二者缺一不可。缺少思想,算法就无法站住,或者可以说固定的模板无法和灵活的题目相联系。缺少实现能力,算法就成了空中楼阁,你想到的思路再清晰再高明,打不出来终究是心有余力不足。
到了如今,最短路问题已经得到了很多种解法。这些解法有相同的地方,也有不同的地方,性能也有所差异。但是,如果一种问题得出的某种解法优于其他解法太多,其他这些解法就应该随时间流逝而被逐渐淘汰。最短路问题的这些解法如今仍屹立不倒,足可说明它们各有偏重的方向。
在我看来,每种算法都由两个部分组成,一部分是思想,另外一部分就是实现能力,二者缺一不可。缺少思想,算法就无法站住,或者可以说固定的模板无法和灵活的题目相联系。缺少实现能力,算法就成了空中楼阁,你想到的思路再清晰再高明,打不出来终究是心有余力不足。
本文所涉及的多种技巧,出自秋叶拓哉的《挑战程序设计》一书。译者提及这些技巧的应用范围都比书中所介绍的模型要广泛,我们应该注重算法技巧中蕴含的算法思想以及思维方式。许多看似复杂困难的问题,关键都可以运用看似简单的技巧处理。我查询网上对于这些技巧的解释,希望能够深化这种技巧蕴含的思想,并且将其变为自己的东西。