夏至的个人博客

递归算法

什么是递归？

递归，在计算机科学中是指一种通过重复把问题分解为同类的子问题而解决问题的方法，通俗来讲，递归表现为函数调用函数本身。在知乎上有一个比喻递归非常形象的例子。 “递归最恰当的比喻，就是查词典。我们使用的词典，本身就是递归，为了解释一个词，需要使用更多的词。当你查一个词，发现这个词的解释中某个词仍然不懂，于是你开始查这第二个词，可惜，第二个词里仍然有不懂的词，于是查第三个词，这样查下去，直到有一个词的解释是你完全能看懂的，那么递归走到了尽头，然后你开始后退，逐个明白之前查过的每一个词，最终，你明白了最开始那个词的意思。”.

分治算法

简要理解

分治算法由三部分组成：

• 分：递归解决较小的问题（基本情况除外）
• 治：从子问题的解构建原问题的解

贪心算法

简要理解

贪心算法是分阶段工作的，在每一个阶段，他都会选择工作它认为眼下所作决定最好的，它是不考虑将来结果的，他只在乎局部最优解，算法终止时，我们希望得到的局部最优的结构就是全局最优，如果是就说明算法是正确的，否则算法得到的是一个次最优解，如果不要求绝对最佳答案，有时可以用简单的贪心算法生成近似答案，它的好处是在处理较大数据，较复杂的问题时，一般时间复杂度与空间复杂度都比产生准确答案的复杂算法要快上很多倍得到一个几乎接近正确的答案。