algorithm-basis-note

algorithm-basis-note

持续更新ing，本文用于记录学习算法过程中的一些较为基础的算法，仅简单介绍！！

递归算法（recursion algorithm）

递归是很多算法实现的基础，是程序设计中一种重要思想和机制，如分治，dfs，dp等算法都用到了递归的思想。

递归概念

递归，在数学与计算机科学中，是指在方法的定义中使用方法自身。也就是说，递归算法是一种直接或者间接调用自身方法的算法。简言之：在定义自身的同时又出现自身的直接或间接调用。

注意：递归必须要有一个退出的条件!

在做递归算法的时候，一定要把握住出口，也就是做递归算法必须要有一个明确的递归结束条件。这一点是非常重要的。其实这个出口是非常好理解的，就是一个条件，当满足了这个条件的时候我们就不再递归了。

递归特点

1）递归就是方法里调用自身。
2）在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。
3）递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。
4）在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等，所以一般不提倡用递归算法设计程序。

递归适用条件

具有以下特征的问题可考虑递归求解：

• 当问题和子问题具有递推关系，比如杨辉三角、计算阶乘（后文讨论）。
• 具有递归性质的数据结构，比如链表、树、图。
• 反向性问题，比如取反。

总结下来，最根本的还是要抓住问题本身是否可以通过层层拆解到最小粒度来得解。

分治算法

分治法是很多高效算法的基础，如排序算法（快速排序，归并排序），傅里叶变换（FFT）等。其中傅里叶变换可以参考一篇没有写在算法专题的伪算法文——CUDA_note_cuFFT

分治概念

在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。即分治法的设计思想是：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

分治特点

• **子问题和原问题性质相同：**分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解或只求一部分子问题的解，就可以得出原问题的解。

• 经常与递归合并使用：如果原问题可分割成k个子问题，1<k≤n，且这些子问题都可解并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。

分治适用条件

分治法所能解决的问题一般具有以下几个特征：

1. 该问题的规模缩小到一定的程度就可以容易地解决。（绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加）

2. 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。（该条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用）

3. 利用该问题分解出的子问题的解可以合并为该问题的解；（如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。）

4. 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。（涉及到分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法（dp）较好。）

枚举算法

枚举概念

在进行归纳推理时，如果逐个考察了某类事件的所有可能情况，因而得出一般结论，那么该结论是可靠 的，这种归纳方法叫做枚举法。将问题的所有可能的答案一一列举，然后根据条件判断此答案是否合适，保留合适的，舍弃不合适的。

枚举特点

• 速度可能很慢
• 实现简单
• 结果正确性高

枚举适用条件

使用该算法需要满足两个条件：
(1)可预先确定候选答案的数量
(2)候选答案的范围在求解之前必须有一个确定的集合

一般限制枚举算法的主要原因来自时间复杂度过高，理论上各类题目在不考虑时间的情况下都可以用枚举算法解决。

贪心算法（greedy algorithm)

贪心概念

贪心算法，又名贪婪法，是寻找最优解问题的常用方法，这种方法模式一般将求解过程分成若干个步骤，但每个步骤都应用贪心原则，选取当前状态下最好/最优的选择（局部最有利的选择），并以此希望最后堆叠出的结果也是最好/最优的解。

贪心特点

1. 贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
2. 一方面局部最优不一定整体最优，但从另一方面而言，贪心在范围相当广泛的问题能产生整体最优解或整体最优解的近似解。

贪心解题一般步骤

1.建立数学模型来描述问题；
2.把求解的问题分成若干个子问题；
3.对每一子问题求解，得到子问题的局部最优解；
4.把子问题的局部最优解合成原来问题的一个解。

基本搜索方法

搜索概念

搜索算法的原理就是枚举。利用计算机的高性能，给出人类制定好的规则，枚举出所有可行的情况，找到可行解或者最优解。

常见的搜索算法

比较常见的搜索算法是 深度优先搜索（又叫深度优先遍历） 和 广度优先搜索（又叫广度优先遍历 或者 宽度优先遍历）。各种图论的算法基本都是依靠这两者进行展开的。

深度优先搜索（dfs）

深度优先搜索用一句话概括就是：“一直往下走，走不通回头，换条路再走，直到无路可走”。

广度优先搜索（bfs）

广度优先搜索会根据离起点的距离，按照从近到远的顺序对各节点进行搜索。

深度优先搜索一般用来求可行解，利用剪枝进行优化，在树形结构的图上用处较多；而广度优先搜索一般用来求最优解，配合哈希表进行状态空间的标记，从而避免重复状态的计算；

搜索算法的优化

剪枝函数

剪枝直接引流另一篇博客——prune-algorithm

双向广度搜索

双向广度优先搜索算法是对广度优先算法的一种扩展。广度优先算法从起始节点以广度优先的顺序不断扩展，直到遇到目的节点；而双向广度优先算法从两个方向以广度优先的顺序同时扩展，一个是从起始节点开始扩展，另一个是从目的节点扩展，直到一个扩展队列中出现另外一个队列中已经扩展的节点，也就相当于两个扩展方向出现了交点，那么可以认为我们找到了一条路径。

双向广度优先算法相对于广度优先算法来说，由于采用了从两个跟开始扩展的方式，搜索树的深度得到了明显的减少，所以在算法的时间复杂度和空间复杂度上都有较大的优势。

双向广度优先算法特别适合于给出了起始节点和目的节点，要求他们之间的最短路径的问题。另外需要说明的是，广度优先的顺序能够保证找到的路径就是最短路径！