JavaScript 基础算法

经典算法

将一个难以直接解决的大问题依照相同的概念分割成两个或更多的子问题，以便各个击破。

递归算法是一种函数调用自身的算法。

递归的基本性质就是函数调用，在处理问题的时候，递归往往是把一个大规模的问题不断地变小然后进行推导的过程。具体来说就是将一个问题的规模变小，然后再利用从小规模问题中得出的结果，结合当前的值或者情况，得出最终的结果。

通俗来说，把要实现的递归函数看成是已经实现好的，直接利用，解决一些子问题，然后需要考虑的就是如何根据子问题的解以及当前面对的情况得出答案。这种算法也被称为自顶向下（Top-Down）算法。

判断当前情况是否非法，如果非法就立即返回，这一步也称为完整性检查（Sanity Check）。例如：看看当前处理的情况是否越界，是否出现了不满足条件的情况。通常，这一部分代码都是写在最前面的
判断是否满足结束递归的条件。在这一步中，处理的基本上都是一些推导过程中所定义的初始情况。
将问题的规模缩小，递归调用。在归并排序和快速排序中将问题的规模缩小了一半，而在汉诺塔或者 leetcode 91 题解码的例子中是将问题的规模缩小了一个。
利用在小规模问题中的答案，结合当前的数据进行整合，得出最终的答案。

贪心法又称贪婪算法，从某一起点开始，在每一个解决问题的步骤中使用贪心原则，即采取在当前状态下最有利或者最优化的选择，不断地改进该解答，持续在每一个步骤中选择最佳方法，并且逐步逼近给定的目标。当达到某一个步骤不能再继续前进时，算法停止，以尽可能快的方法求得更好的解。

贪心法的解题思路尽管是把求解的问题拆分成若干个子问题，不过有时候还是不能保成求得的解是最佳或者最优化的，因为贪心法容易过早做出决定，所以只能求出满足某些约束条件的解。

动态规划类似于分治法，用于研究多阶段决策过程的优化过程与求得一个问题的最优解。

动态规划法的主要做法是：如果一个问题的答案与子问题相关，就能将大问题拆解成各个小问题。其中与分治法最大的不同是可以将每一个子问题的答案存储起来，以供下次求解时直接取用。

这样的做法不但可以减少再次计算的时间，而且可以将这些解组合成大问题的解，故而可以解决重复计算的问题。

迭代法无法使用公式一次求解，而需要使用重复结构（即循环）重复执行一段程序代码来得到答案。

枚举法又称为穷举法，是一种常见的数学方法，核心思想是列举所有的可能。

根据问题的要求逐一列举问题的解答，或者为了便于解决问题把问题分为不重复，不遗漏的有限种情况，逐一列举各种情况，并加以解决，最终达到解决整个问题的目的。

像枚举法这种分析问题、解决问题的方法，得到的结果总是正确的，缺点是速度太慢。

回溯实际上是一种试探算法，这种算法跟暴力搜索最大的不同在于，在回溯算法里，是一步一步地小心翼翼地进行向前试探，会对每一步探测到的情况进行评估，如果当前的情况已经无法满足要求，那么就没有必要继续进行下去。

回溯算法的特点在于，当出现非法的情况时，算法可以回退到之前的情景，可以是返回一步，有时候甚至可以返回多步，然后再去尝试别的路径和办法。这也就意味着，想要采用回溯算法，就必须保证每次都有多种尝试的可能。

Last updated 9 days ago

Was this helpful?