程序员常用的十一种算法

程序员常用的十一种算法程序员常用的十一种算法1.二分查找算法2.分治法3.动态规划4.字符串暴力匹配算法5.KMP算法6.贪心算法7.普里姆算法介绍(找点)8.克鲁斯卡尔(Kruskal)算法(找边)9.迪杰斯特拉算法10.弗洛伊德算法11.骑士周游回溯算法


算法介绍

程序员常用的十一种算法

1.二分查找算法

将数组分为三部分,依次是中值(所谓的中值就是数组中间位置的那个值)前,中值,中值后;将要查找的值和数组的中值进行比较,若小于中值则在中值前 面找,若大于中值则在中值后面找,等于中值时直接返回。然后依次是一个递归过程,将前半部分或者后半部分继续分解为三部分。

2.分治法

分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题。

解决:若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题;解决:若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题。

合并:将各个子问题的解合并为原问题的解。

3.动态规划

动态规划是将问题分解成若干个子问题,依次求解子问题,且前一个子问题的解为后一个子问题的求解提供信息。最后一个子问题的解即为原问题的解。

动态规划中的每个子问题只求解一次,一旦子问题的解被求出,则将该解存储起来,方便之后的子问题求解。相比递归算法,动态规划中每个子问题只求解一次,具有天然的剪枝功能,大大减少了计算量与时间。

动态规划三要素
状态转移方程
最优子结构
边界

针对问题,设计状态转移方程,寻找最优子结构和边界。这是实现动态规划的关键。

4.字符串暴力匹配算法

1.如果当前字符匹配成功(即str1[i] == str2[j]),则i++,j++,继续匹配下一个字符。

2.如果失配(即str1[i] != str2[j]),令i=i-(j-1),j = 0。相当于每次匹配失败时,i回溯,j被置为0。

3.用暴力方法解决问题的话会有大量的回溯,每次只移动一位,若是不匹配,移动到下一位接着判断,浪费了大量的时间。

5.KMP算法

KMP算法时一个解决模式串在文本串是否出现过,如果出现过,返回最早出现的位置的经典算法。
Knuth-Morris-Pratt字符串查找算法,简称KMP算法。
KMP算法通过利用之前判断该信息,通过一个next数组,保存模式串中前后最长公共子序列的长度,
每次回溯时,通过next数组找到,前面匹配过的位置,省去大量时间。

6.贪心算法

贪心算法的基本思路:
1.建立数学模型来描述问题。
2.把求解的问题分成若干个子问题。
3.对每一子问题求解,得到子问题的局部最优解。
4.把子问题的解局部最优解合成原来解问题的一个解。

7.普里姆算法介绍(找点)

普利姆(Prim)算法求最小生成树,也就是在包含n个顶点的连通图中,找出只有(n-1)条边包含所有n个顶点的连通子图,也就是所谓的极小连通子图
普里姆算法如下:

(1)设G=(V,E)是连通网,T=(U,D)是最小生成树,V,U是顶点集合,E,D是边的集合
(2)若从顶点u开始构造最小生成树,则从集合v中取出顶点u放入集合U中,标记顶点v的visited[u] = 1
(3)若集合U中顶点ui与集合V-U中的顶点vj之间存在边,则寻找这些边中权值最小的边,单不能构成回路,将顶点vj加入集合U中,将边(ui,vj)加入集合D中,标记visited[vj]=1
(4)重复步骤2,知道U,V相等,即所有顶点都被标记为访问过,此时D中有n-1条边

8.克鲁斯卡尔(Kruskal)算法(找边)

基本思想:按照权值从小到大的顺序选择n-1条边,并保证n-1条边不构成回路

具体做法:首先构造一个只含有n个顶点的森林,然后依权值从小到大从连通网中选择加入到森林中,并是森林中不产生回路,直到森林变成一棵树为止

9.迪杰斯特拉算法

基本思想
通过Dijkstra计算图G中的最短路径时,需要指定起点s(即从顶点s开始计算)。

此外,引进两个集合S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度),
而U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离)。
初始时,S中只有起点s;U中是除s之外的顶点,并且U中顶点的路径是"起点s到该顶点的路径"。
然后,从U中找出路径最短的顶点,并将其加入到S中;接着,更新U中的顶点和顶点对应的路径。
 然后,再从U中找出路径最短的顶点,并将其加入到S中;接着,更新U中的顶点和顶点对应的路径。
  ... 重复该操作,直到遍历完所有顶点。

操作步骤
(1) 初始时,S只包含起点s;U包含除s外的其他顶点,且U中顶点的距离为”起点s到该顶点的距离”[例如,U中顶点v的距离为(s,v)的长度,然后s和v不相邻,则v的距离为∞]。
(2) 从U中选出”距离最短的顶点k”,并将顶点k加入到S中;同时,从U中移除顶点k。
(3) 更新U中各个顶点到起点s的距离。之所以更新U中顶点的距离,是由于上一步中确定了k是求出最短路径的顶点,从而可以利用k来更新其它顶点的距离;例如,(s,v)的距离可能大于(s,k)+(k,v)的距离。
(4) 重复步骤(2)和(3),直到遍历完所有顶点。

10.弗洛伊德算法

算法描述

在有向图 G=(V,E) 中,假设每条边 E[i] 的长度为 w[i],找到V钟任意两点之间的路径长度最小值。
弗洛伊德算法选取某个节点k作为i到j需要经过的中间节点,通过比较d(i,k)+d(k,j)和现有d(i,j)的大小,将较小值更新为路径长度,对k节点的选取进行遍历,以得到在经过所有节点时i到j的最短路径长度,通过不断加入中间点的方式更新最短路径。同时在path数组中存储i到j所经过的中间节点k,用于最后递归调用输出路径结果。
贪心算法适用的问题
贪心策略适用的前提是:局部最优策略能导致产生全局最优解。也就是当算法终止的时候,局部最优等于全局最优。

11.骑士周游回溯算法

主要思想:深度优先遍历+回溯+贪心。从初始位置startPoint开始,获取下一步能到达的所有位置,将它们添加到集合ArrayList< Point >中,根据它们下一步所能到达的位置的个数k对ArrayList< Point >中所有位置进行非递减排序,优先对k较小的位置进行遍历,若此路不通,则回溯。

我的学习论坛

HandsomeForum:用Java编写的学习论坛,打造我们自己的圈子!(http://huangjunjie.vip:66)
文章链接:http://huangjunjie.vip:66/blog/read/u3zdadmc7ectoamsqm

今天的文章程序员常用的十一种算法分享到此就结束了,感谢您的阅读,如果确实帮到您,您可以动动手指转发给其他人。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/33509.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注