• 首页
        • 更多产品

          客户为中心的产品管理工具

          专业的软件研发项目管理工具

          简单易用的团队知识库管理

          可量化的研发效能度量工具

          测试用例维护与计划执行

          以团队为中心的协作沟通

          研发工作流自动化工具

          账号认证与安全管理工具

          Why PingCode
          为什么选择 PingCode ?

          6000+企业信赖之选,为研发团队降本增效

        • 行业解决方案
          先进制造(即将上线)
        • 解决方案1
        • 解决方案2
  • Jira替代方案
目录

高级算法有哪些

高级算法有:1. 穷竭搜索;2. 贪心;3. 动态规划;4. 图论;5. 数论。其中,深度优先搜索(DFS)从某个状态开始,不断转移,直至无法转移,回退到前一步,再继续转移到其他状态,直到找到最终解。

一、高级算法

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)。

延伸阅读:

二、 分治法特征

该问题的规模缩小到一定的程度就可以容易地解决 。
该问题可以分解为若干个规模较小的相同问题,即该问题具有优异子结构性质。
利用该问题分解出的子问题的解可以合并为该问题的解。
该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子问题。

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

相关文章