02 October 2014
最近在算法课上，遇到了一个很有意思的题目，题目的大意是寻找空间中的最近点对。 给定空间上的n个节点，如何查找这n个点对中最近的点对的距离? 这里的距离采用欧氏距离 朴素法 朴素法是最为简单和粗暴的办法，具体思想是枚举空间中所有可能的点对，并且分别计算这些点对之间的距离。这些点对之间的最小距离即是答案。 朴素法需要分别枚举i和j，算法的时间复杂度为。 分治法 分治法的基本思想是将一个问题分解成几个更小的子问题，求解并合并这些子问题作为这个问题的结果。当子问题足够小的时候便可以直接求解。因此，分治法的解法分为两个步骤，分解和合并。 分解 我们的问题是求解这n个节点中的最近点对，那么如何该分解...
29 July 2014
本文从blog.163.com/kazenoyume@126/上迁移过来 最近在工作之余，参加了hihocoder推出的编程提高班。这个编程提高班真的很有意思，它的讲课内容是跟算法分析设计有关的。而这周讲课的内容，是大家都耳熟能详的KMP算法。 在大二的时候，我曾经学习过KMP算法，当时还刷了好几道OJ题，所以就理所当然的以为这周的算法题目是相当的简单，不需要花很多时间就能完成的了。但是当我开始做题目的时候，我却发现自己完全不懂KMP算法！当初学习KMP算法的时候，只是对算法有个直观上的了解，就只知道它的时间复杂度和空间复杂度，完全只把它当作API来用。而且当时学习的时候也是晕头转向的，...