一、高级算法

1. 穷竭搜索

深度优先搜索（DFS）：

从某个状态开始，不断转移，直至无法转移，回退到前一步，再继续转移到其他状态，直到找到最终解。通常采用递归函数或者栈（Stack）来实现。

宽度优先搜索（BFS）：

从初始状态开始，总是先搜索至距离初始状态近的状态。每个状态都只经过一次，因此复杂度为O(状态数*转移方式数)。通常采用循环或队列（Queue）实现。

2. 贪心

贪心算法：

遵循某种规律，不断贪心选取当前优异策略。

贪心证明：

与其它选择方案相比，该算法并不会得到更差的解（归纳法）；不存在其他的解决方案（反证法）。

3. 动态规划

动态规划（DP）：

通过定义某种优异子状态，进行状态间转移达到最终解。

记忆化搜索：

将重复状态通过标记降低复杂度。

多种形式的DP：

搜索的记忆化或利用递推关系的DP，或从状态转移考虑的DP。状态定义和循环顺序都会影响复杂度。

4. 图论

图：

顶点集合为V、边集为E的图记作G=(V,E)，从u到v的边记作e=(u,v)。根据边是否有向分为有向图和无向图，根据是否有环分为有环图和无环图。图可由邻接表和邻接矩阵两种方式表示。

Bellman-Ford算法（单源最短路）：

记录起点到每个点i的最短距离d[i]，用所有的边条件持续更新d[i]，直到每个d[i]都已经为最小无法更新。图可包含负权边，包含负环的判断方法为将所有d[i]初始化为0，第V次d[i]是否仍存在更新。复杂度为O(EV)。

Dijkstra算法（单源最短路）：

从起点出发出发，更新s所有可到达的边j，若d[j]有更新，则加入最小堆，以便下次找到剩余集合中d[i]最小的点i，再从i出发BFS，直到到达终点t。不能处理包含负权边的图。复杂度为O(ElogV)。

Floyd-Warshall算法（多源最短路）：

定义从i到j且经过k的最短路为d[i][j]用d[i][k]+d[k][j]来更新，三重循环直接得到任意两点间的最短路。图可包含负权边，包含负环的判断方法为是否存在顶点i使d[i][i]为负。复杂度O(V^3)。

Prim算法（最小生成树）：

假设V的子集X已经构造了部分最小生成树，那么接下来就是选取从X到X的补集中权值最小的边加入。可使用最小堆维护待选的边，复杂度为O(ElogV)。

Kruskal算法（最小生成树）：

将所有边升序排列，依次取出每条最小的边，若该边的两个端点不在相同并查集内，则将该边加入最小生成树，并将两点用并查集连接。耗时非常多的操作为边的排序，复杂度O(ElogE)。

5. 数论

辗转相除算法（最小公约数）：

gcd(a,b)=gcd(b,a%b)，循环至b为0，此时得到最小公约数为a。

扩展欧几里德算法（解二元一次方程）：

求解ax+by=gcd(a,b)，类似辗转相除法。求extgcd(a,b,&x,&y)时，递归求得d=extgcd(b,a%b,y,x)的解存入y和x。则ax+by=gcd(a,b)的解为x和y-(a/b)*x。

素数筛法：

通过已求得的素数，将所求范围内所有该素数的倍数都标记为合数。依序遍历空间，未被筛掉的即为新的素数。复杂度O(nloglogn)，可看作线性的。

反复平方法（快速幂）：求x的n次幂，可二分递归求x的n/2次幂，即x^n=(x^(n/2))^2 *

x^(n&1)。复杂度为O(logn)。

延伸阅读：

二、分治法的特征

该问题的规模缩小到一定的程度就可以容易地解决 。

该问题可以分解为若干个规模较小的相同问题，即该问题具有优异子结构性质。

利用该问题分解出的子问题的解可以合并为该问题的解。

该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

以上就是关于高级算法的内容希望对大家有帮助。

上一篇

什么是容器即服务（CaaS）?

下一篇

什么是基础设施即代码?