
- 特 征
- 有穷性 确切性 输入 输出 可行
- 常 用
- 计算、数据处理和自动推理
- 外文名
- Algorithm
- 中文名
- 算法
- 学 科
- 数学 计算机
-
算法
2018-02-08 00:13:091.算法定义 算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出...1.算法定义
算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。如果一个算法有缺陷,或不适合于某个问题,执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
- 一个算法应该具有以下七个重要的特征:
- ①有穷性(Finiteness):算法的有穷性是指算法必须能在执行有限个步骤之后终止;
②确切性(Definiteness):算法的每一步骤必须有确切的定义;
③输入项(Input):一个算法有0个或多个输入,以刻画运算对象的初始情况,所谓0个输 入是指算法本身定出了初始条件;
④输出项(Output):一个算法有一个或多个输出,以反映对输入数据加工后的结果。没 有输出的算法是毫无意义的;
⑤可行性(Effectiveness):算法中执行的任何计算步骤都是可以被分解为基本的可执行 的操作步,即每个计算步都可以在有限时间内完成(也称之为有效性);
⑥高效性(High efficiency):执行速度快,占用资源少;
⑦健壮性(Robustness):对数据响应正确。
2. 时间复杂度
计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间,时间复杂度常用大O符号(大O符号(Big O notation)是用于描述函数渐进行为的数学符号。更确切地说,它是用另一个(通常更简单的)函数来描述一个函数数量级的渐近上界。在数学中,它一般用来刻画被截断的无穷级数尤其是渐近级数的剩余项;在计算机科学中,它在分析算法复杂性的方面非常有用。)表述,使用这种方式时,时间复杂度可被称为是渐近的,它考察当输入值大小趋近无穷时的情况。
大O,简而言之可以认为它的含义是“order of”(大约是)。
无穷大渐近
大O符号在分析算法效率的时候非常有用。举个例子,解决一个规模为 n 的问题所花费的时间(或者所需步骤的数目)可以被求得:T(n) = 4n^2 - 2n + 2。 当 n 增大时,n^2; 项将开始占主导地位,而其他各项可以被忽略——举例说明:当 n = 500,4n^2; 项是 2n 项的1000倍大,因此在大多数场合下,省略后者对表达式的值的影响将是可以忽略不计的。
3.时间复杂度计算方法
1.一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。
一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。2.一般情况下,算法的基本操作重复执行的次数是模块n的某一个函数f(n),因此,算法的时间复杂度记做:T(n)=O(f(n))。随着模块n的增大,算法执行的时间的增长率和f(n)的增长率成正比,所以f(n)越小,算法的时间复杂度越低,算法的效率越高。
在计算时间复杂度的时候,先找出算法的基本操作,然后根据相应的各语句确定它的执行次数,再找出T(n)的同数量级(它的同数量级有以下:1,Log2n ,n ,nLog2n ,n的平方,n的三次方,2的n次方,n!),找出后,f(n)=该数量级,若T(n)/f(n)求极限可得到一常数c,则时间复杂度T(n)=O(f(n))。3.常见的时间复杂度
按数量级递增排列,常见的时间复杂度有:
常数阶O(1), 对数阶O(log2n), 线性阶O(n), 线性对数阶O(nlog2n), 平方阶O(n^2), 立方阶O(n^3),…, k次方阶O(n^k), 指数阶O(2^n) 。- 其中,
- 1.O(n),O(n^2), 立方阶O(n^3),…, k次方阶O(n^k) 为多项式阶时间复杂度,分别称为一阶时间复杂度,二阶时间复杂度。。。。
2.O(2^n),指数阶时间复杂度,该种不实用
3.对数阶O(log2n), 线性对数阶O(nlog2n),除了常数阶以外,该种效率最高
例:算法: for(i=1;i<=n;++i) { for(j=1;j<=n;++j) { c[ i ][ j ]=0; //该步骤属于基本操作 执行次数:n^2 for(k=1;k<=n;++k) c[ i ][ j ]+=a[ i ][ k ]*b[ k ][ j ]; //该步骤属于基本操作 执行次数:n^3 } } 则有 T(n)= n^2+n^3,根据上面括号里的同数量级,我们可以确定 n^3为T(n)的同数量级 则有f(n)= n^3,然后根据T(n)/f(n)求极限可得到常数c 则该算法的 时间复杂度:T(n)=O(n^3)
4.讨论
定义:如果一个问题的规模是n,解这一问题的某一算法所需要的时间为T(n),它是n的某一函数 T(n)称为这一算法的“时间复杂性”。
当输入量n逐渐加大时,时间复杂性的极限情形称为算法的“渐近时间复杂性”。
我们常用大O表示法表示时间复杂性,注意它是某一个算法的时间复杂性。大O表示只是说有上界,由定义如果f(n)=O(n),那显然成立f(n)=O(n^2),它给你一个上界,但并不是上确界,但人们在表示的时候一般都习惯表示前者。
此外,一个问题本身也有它的复杂性,如果某个算法的复杂性到达了这个问题复杂性的下界,那就称这样的算法是最佳算法。
“大O记法”:在这种描述中使用的基本参数是 n,即问题实例的规模,把复杂性或运行时间表达为n的函数。这里的“O”表示量级 (order),比如说“二分检索是 O(logn)的”,也就是说它需要“通过logn量级的步骤去检索一个规模为n的数组”记法 O ( f(n) )表示当 n增大时,运行时间至多将以正比于 f(n)的速度增长。
这种渐进估计对算法的理论分析和大致比较是非常有价值的,但在实践中细节也可能造成差异。例如,一个低附加代价的O(n2)算法在n较小的情况下可能比一个高附加代价的 O(nlogn)算法运行得更快。当然,随着n足够大以后,具有较慢上升函数的算法必然工作得更快。
O(1) Temp=i;i=j;j=temp; 以上三条单个语句的频度均为1,该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶,记作T(n)=O(1)。如果算法的执行时间不随着问题规模n的增加而增长,即使算法中有上千条语句,其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。 O(n^2) 2.1. 交换i和j的内容 sum=0; (一次) for(i=1;i<=n;i++) (n次 ) for(j=1;j<=n;j++) (n^2次 ) sum++; (n^2次 ) 解:T(n)=2n^2+n+1 =O(n^2) 2.2. for (i=1;i<n;i++) { y=y+1; ① for (j=0;j<=(2*n);j++) x++; ② } 解: 语句1的频度是n-1 语句2的频度是(n-1)*(2n+1)=2n^2-n-1 f(n)=2n^2-n-1+(n-1)=2n^2-2 该程序的时间复杂度T(n)=O(n^2). O(n) 2.3. a=0; b=1; ① for (i=1;i<=n;i++) ② { s=a+b; ③ b=a; ④ a=s; ⑤ } 解:语句1的频度:2, 语句2的频度: n, 语句3的频度: n-1, 语句4的频度:n-1, 语句5的频度:n-1, T(n)=2+n+3(n-1)=4n-1=O(n). O(log2n ) 2.4. i=1; ① while (i<=n) i=i*2; ② 解: 语句1的频度是1, 设语句2的频度是f(n), 则:2^f(n)<=n;f(n)<=log2n 取最大值f(n)= log2n, T(n)=O(log2n ) O(n^3) 2.5. for(i=0;i<n;i++) { for(j=0;j<i;j++) { for(k=0;k<j;k++) x=x+2; } } 解:当i=m, j=k的时候,内层循环的次数为k当i=m时, j 可以取 0,1,...,m-1 , 所以这里最内循环共进行了0+1+...+m-1=(m-1)m/2次所以,i从0取到n, 则循环共进行了: 0+(1-1)*1/2+...+(n-1)n/2=n(n+1)(n-1)/6所以时间复杂度为O(n^3).
我们还应该区分算法的最坏情况的行为和期望行为。如快速排序的最 坏情况运行时间是 O(n^2),但期望时间是 O(nlogn)。通过每次都仔细地选择基准值,我们有可能把平方情况 (即O(n^2)情况)的概率减小到几乎等于 0。在实际中,精心实现的快速排序一般都能以 (O(nlogn)时间运行。
- 下面是一些常用的记法:
- 访问数组中的元素是常数时间操作,或说O(1)操作。一个算法如 果能在每个步骤去掉一半数据元素,如二分检索,通常它就取 O(logn)时间。用strcmp比较两个具有n个字符的串需要O(n)时间。常规的矩阵乘算法是O(n^3),因为算出每个元素都需要将n对 元素相乘并加到一起,所有元素的个数是n^2。
指数时间算法通常来源于需要求出所有可能结果。例如,n个元 素的集合共有2n个子集,所以要求出所有子集的算法将是O(2n)的。指数算法一般说来是太复杂了,除非n的值非常小,因为,在 这个问题中增加一个元素就导致运行时间加倍。不幸的是,确实有许多问题 (如著名的“巡回售货员问题” ),到目前为止找到的算法都是指数的。如果我们真的遇到这种情况,通常应该用寻找近似最佳结果的算法替代之。
5.常用排序
-
为有机会进大厂,程序员必须掌握的核心算法有哪些?
2019-10-21 12:11:41由于我之前一直强调数据结构以及算法学习的重要性,所以就有一些读者经常问我,数据结构与算法应该要学习到哪个程度呢?,说实话,这个问题我不知道要怎么回答你,主要取决于你想学习到哪些程度,不过针对这个问题,...由于我之前一直强调数据结构以及算法学习的重要性,所以就有一些读者经常问我,数据结构与算法应该要学习到哪个程度呢?,说实话,这个问题我不知道要怎么回答你,主要取决于你想学习到哪些程度,不过针对这个问题,我稍微总结一下我学过的算法知识点,以及我觉得值得学习的算法。这些算法与数据结构的学习大多数是零散的,并没有一本把他们全部覆盖的书籍。下面是我觉得值得学习的一些算法以及数据结构,当然,我也会整理一些看过不错的文章给大家。大家也可以留言区补充。
一、算法最最基础
1、时间复杂度
2、空间复杂度
一般最先接触的就是时间复杂度和空间复杂度的学习了,这两个概念以及如何计算,是必须学的,也是必须最先学的,主要有最大复杂度、平均复杂度等,直接通过博客搜索学习即可。
文章推荐:
二、基础数据结构
1、线性表
- 列表(必学)
- 链表(必学)
- 跳跃表(知道原理,应用,最后自己实现一遍)
- 并查集(建议结合刷题学习)
不用说,链表、列表必须,不过重点是链表。
2、栈与队列
- 栈(必学)
- 队列(必学)
- 优先队列、堆(必学)
- 多级反馈队列(原理与应用)
特别是优先队列,再刷题的时候,还是经常用到的,队列与栈,是最基本的数据结构,必学。可以通过博客来学习。相关文章:
3、哈希表(必学)
- 碰撞解决方法:开放定址法、链地址法、再次哈希法、建立公共溢出区(必学)
- 布隆过滤器(原理与应用)
哈希表相关的,推荐通过博客来学习,推荐文章:
4、树
- 二叉树:各种遍历(递归与非递归)(必学)
- 哈夫曼树与编码(原理与应用)
- AVL树(必学)
- B 树与 B+ 树(原理与应用)
- 前缀树(原理与应用)
- 红黑树(原理与应用)
- 线段树(原理与应用)
树相关是知识还是挺多的,建议看书,可以看《算法第四版》。相关文章:
高频面试题:什么是B树?为啥文件索引要用B树而不用二叉查找树?
5、数组
- 树状数组
- 矩阵(必学)
树状数组其实我也没学过,,,,
三、各种常见算法
1、十大排序算法
- 简单排序:插入排序、选择排序、冒泡排序(必学)
- 分治排序:快速排序、归并排序(必学,快速排序还要关注中轴的选取方式)
- 分配排序:桶排序、基数排序
- 树状排序:堆排序(必学)
- 其他:计数排序(必学)、希尔排序
对于十大算法的学习,假如你不大懂的话,那么我还是挺推荐你去看书的,因为看了书,你可能不仅仅知道这个算法怎么写,还能知道他是怎么来的。推荐书籍是《算法第四版》,这本书讲的很详细,而且配了很多图演示,还是挺好懂的。
推荐文章:
必学十大经典排序算法,看这篇就够了(附完整代码/动图/优质文章)(修订版)
2、图论算法
- 图的表示:邻接矩阵和邻接表
- 遍历算法:深度搜索和广度搜索(必学)
- 最短路径算法:Floyd,Dijkstra(必学)
- 最小生成树算法:Prim,Kruskal(必学)
- 实际常用算法:关键路径、拓扑排序(原理与应用)
- 二分图匹配:配对、匈牙利算法(原理与应用)
- 拓展:中心性算法、社区发现算法(原理与应用)
图还是比较难的,不过我觉得图涉及到的挺多算法都是挺实用的,例如最短路径的计算等,图相关的,我这里还是建议看书的,可以看《算法第四版》。
更多算法的学习,欢迎关注我的公众号『帅地玩编程』
3、搜索与回溯算法
- 贪心算法(必学)
- 启发式搜索算法:A*寻路算法(了解)
- 地图着色算法、N 皇后问题、最优加工顺序
- 旅行商问题
这方便的只是都是一些算法相关的,我觉得如果可以,都学一下。像贪心算法的思想,就必须学的了。建议通过刷题来学习,leetcode 直接专题刷。
4、动态规划
- 树形DP:01背包问题
- 线性DP:最长公共子序列、最长公共子串
- 区间DP:矩阵最大值(和以及积)
- 数位DP:数字游戏
- 状态压缩DP:旅行商
我觉得动态规划是最难的一个算法思想了,记得当初第一次接触动态规划的时候,是看01背包问题的,看了好久都不大懂,懵懵懂懂,后面懂了基本思想,可是做题下不了手,但是看的懂答案。一气之下,再leetcdoe专题连续刷了几十道,才掌握了动态规划的套路,也有了自己的一套模板。不过说实话,动态规划,是考的真他妈多,学习算法、刷题,一定要掌握。这里建议先了解动态规划是什么,之后 leetcode 专题刷,反正就一般上面这几种题型。后面有时间,我也写一下我学到的套路,有点类似于我之前写的递归那样,算是一种经验。也就是我做题时的模板,不过感觉得写七八个小时,,,,,有时间就写。之前写的递归文章:为什么你学不会递归?告别递归,谈谈我的一些经验
5、字符匹配算法
- 正则表达式
- 模式匹配:KMP、Boyer-Moore
我写过两篇字符串匹配的文章,感觉还不错,看了这两篇文章,我觉得你就差不多懂 kmp 和 Boyer-Moore 了。
字符串匹配Boyer-Moore算法:文本编辑器中的查找功能是如何实现的?
更多算法的学习,欢迎关注我的公众号『苦逼的码农』
6、流相关算法
- 最大流:最短增广路、Dinic 算法
- 最大流最小割:最大收益问题、方格取数问题
- 最小费用最大流:最小费用路、消遣
这方面的一些算法,我也只了解过一些,感兴趣的可以学习下。
总结
对于上面设计到的算法,我都提供了感觉还不错的文章,建议大家收藏,然后可以利用零碎的时间进行阅读,有些人可能会觉得上面的算法太多,说实话,我觉得不多,特别是对于在校生的,上面涉及到的算法可以不用很懂,但至少得了解。至于书籍的话,如果你连基本数据结构都还不懂的,建议看《数据结构与算法》相关书籍,例如《大话数据结构》、《数据结构与算法分析》。如果你有一定的基础,例如知道链表,栈,队列,那么可以看《算法第四版》,不过这本书是用 Java 实现的,不过我觉得你只要学过 C,那么可以看的懂。
这些算法的学习,虽然你觉得学了没有什么用,但还是那些话,它对你的影响是潜意识的,它可以给你打下很深厚的基础内功,如果你想走的更远,那么我推荐学习,标注必学的,那么我觉得,你是真的需要抽时间来学习下,标注原理与应用的,代表你可以不知道怎么用代码实现,但是必得知道它的实现原理以及应用,更多算法的学习,可以持续关注我的微信公众号勒。
作为一个非常注重计算机基础以及算法学习的程序员,一路自学走来,看过挺多不错的优质书籍,在这里推荐给大家,全都是自己看过滴。
最后,很多人问我都是怎么学习的,那我干脆就把我看过的优质书籍贡献出来:
计算机基础入门推荐:《程序是怎样跑起来的》、《网络是怎样连接的》、《计算机是怎样工作的》
进一步认识计算机网络:《计算机网络:自顶向下》、《图解http》
数据结构+算法入门:《数据结构与算法分析:C语言描述版》,《大话数据结构》、《阿哈算法》
算法进阶:《算法第四版》、《编程之美》、《编程珠玑》
由于我是Java技术栈的,顺便推荐基本Java的书籍,从左到由的顺序看到
Java:《Java核心技术卷1》、《编程思想》、《深入理解Java虚拟机》、《Java编程艺术》
数据库:《mysql必知必会》、《MySQL技术内幕:InnoDB存储引擎》
就先介绍这么多,这些都是最基础最核心滴,希望对那些不知道看什书的同学有所帮助
对了,我介绍的这些书籍,我顺便帮你整理好了,你可以在我的原创微信公众号『帅地玩编程』回复『书籍』获取哦
另外,帅地把公众号的精华文章整理成了一本电子书,共 630页!目录如下
现在免费送给大家,在我的公众号帅地玩编程回复程序员内功修炼即可获取。有收获?希望老铁们来个三连击,给更多的人看到这篇文章
1、老铁们,关注我的原创微信公众号「帅地玩编程」,专注于写算法 + 计算机基础知识(计算机网络+ 操作系统+数据库+Linux),保存让你看完有所收获,不信你打我。
2、给俺点个赞呗,可以让更多的人看到这篇文章,顺便激励下我,嘻嘻。
作者info
作者:帅地,一位热爱写作的小伙
原创公众号:『帅地玩编程』,已写了150多篇文章,专注于写 算法、计算机基础知识等提升你内功的文章,期待你的关注。
转载说明:务必注明来源(注明:来源于公众号:苦逼的码农, 作者:帅地) -
程序员面试、算法研究、编程艺术、红黑树、机器学习5大系列集锦
2011-06-14 12:11:00程序员面试、算法研究、编程艺术、红黑树、机器学习5大经典原创系列集锦与总结 作者:July--结构之法算法之道blog之博主。 时间:2010年10月-2018年5月,一直在不断更新中.. 出处:...程序员面试、算法研究、编程艺术、红黑树、机器学习5大经典原创系列集锦与总结
作者:July--结构之法算法之道blog之博主。
时间:2010年10月-2018年5月,一直在不断更新中..
出处:http://blog.csdn.net/v_JULY_v 。
说明:本博客中部分文章经过不断修改、优化,已集结出版成书《编程之法:面试和算法心得》。前言
开博4年有余,回首这4年,自己的研究兴趣从最初的编程、面试、数据结构、算法,转移到最近的数据挖掘、机器学习之上,而自己在本blog上也着实花费了巨大的时间和精力,写的东西可能也够几本书的内容了。然不管怎样,希望我能真真正正的为读者提供实实在在的价值与帮助。下面,敬请观赏。有任何问题,欢迎随时不吝指正(同时,若你也能帮助回复blog内留言的任何朋友的问题,欢迎你随时不吝分享&回复,我们一起讨论,互帮互助,谢谢)。
无私分享,造福天下
以下是本blog内的微软面试100题系列,经典算法研究系列,程序员编程艺术系列,红黑树系列,及数据挖掘十大算法等5大经典原创系列作品与一些重要文章的集锦:
一、微软面试100题系列- 横空出世,席卷Csdn--评微软等数据结构+算法面试100题 (微软面试100题系列原题+答案索引)
- 微软100题 (微软面试完整第1-100题)
- 微软面试100题2010年版全部答案集锦(含下载地址)
- 全新整理:微软、谷歌、百度等公司经典面试100题[第101-160题]
- 全新整理:微软、Google等公司的面试题及解答[第161-170题]
- 十道海量数据处理面试题与十个方法大总结 (十道海量数据处理面试题)
- 海量数据处理面试题集锦与Bit-map详解 (十七道海量数据处理面试题)
- 教你如何迅速秒杀掉:99%的海量数据处理面试题 (海量数据处理PDF)
- 九月腾讯,创新工场,淘宝等公司最新面试三十题(第171-200题) (2011年度九月最新面试三十题)
- 十月上旬百度,阿里巴巴,迅雷搜狗最新面试七十题(第201-270题) (2011年度十月上旬七十题)
- 十月下旬腾讯,网易游戏,百度最新校园招聘笔试题集锦(第271-330题) (2011年度十月下旬校招)
- 九月十月百度人搜,阿里巴巴,腾讯华为笔试面试八十题(第331-410题) (2012年度笔试面试八十题)
- 九月百度,迅雷,华为,阿里巴巴,最新校招笔试面试十(第411-470题) (2013年度校招笔试面试十题)
上述微软面试100题系列(共计11篇文章,300多道面试题)的PDF文档近期已经制作出来,其下载地址为:http://download.csdn.net/detail/v_july_v/4583815。
- 一、A*搜索算法
- 一(续)、A*,Dijkstra,BFS算法性能比较及A*算法的应用
- 二、Dijkstra 算法初探 (Dijkstra算法系列4篇文章)
- 二(续)、彻底理解Dijkstra算法
- 二(再续)、Dijkstra 算法+fibonacci堆的逐步c实现
- 二(三续)、Dijkstra 算法+Heap堆的完整c实现源码
- 三、dynamic programming
- 四、BFS和DFS优先搜索算法
- 五、教你透彻了解红黑树 (红黑树系列6篇文章之其中两篇)
- 五(续)、红黑树算法的实现与剖析
- 六、教你初步了解KMP算法
- 六(续)、从KMP算法一步一步谈到BM算法
- 六(三续)、从头到尾彻底理解KMP (KMP的PDF)
- 七、遗传算法 透析GA本质
- 八、再谈启发式搜索算法
- 九、图像特征提取与匹配之SIFT算法 (sift算法系列五篇文章)
- 九(续)、sift算法的编译与实现
- 九(再续)、教你一步一步用c语言实现sift算法、上
- 九(再续)、教你一步一步用c语言实现sift算法、下
- 九(三续):SIFT算法的应用--目标识别之Bag-of-words模型
- 九(四续)、SIFT + KD_BBF算法 (此文第3部分)
- 十、从头到尾彻底理解傅里叶变换算法、上
- 十、从头到尾彻底理解傅里叶变换算法、下
- 十一、从头到尾彻底解析Hash表算法
- 十一(续)、倒排索引关键词Hash不重复编码实践
- 十二、快速排序算法 (快速排序算法3篇文章)
- 十二(续)、快速排序算法的深入分析
- 十二(再续):快速排序算法之所有版本的c/c++实现
- 十三、通过浙大上机复试试题学SPFA 算法
- 十四、快速选择SELECT算法的深入分析与实现
- 十五、多项式乘法与快速傅里叶变换
最新的十五个经典算法研究的PDF文档0积分下载地址如下(1个月5000+人次下载):http://download.csdn.net/detail/v_july_v/4478027。
「此外原来的十三个经典算法研究[带目录+标签]的PDF文档,Csdn下载地址:http://download.csdn.net/source/3427838;新浪爱问共享下载地址:http://ishare.iask.sina.com.cn/f/16968707.html 」。
- 第一章、左旋转字符串
- 第二章、字符串是否包含问题
- 第三章、寻找最小的k个数
- 第三章续、Top K算法问题的实现
- 第三章再续:快速选择SELECT算法的深入分析与实现
- 三之三续、求数组中给定下标区间内的第K小(大)元素
- 第四章、现场编写类似strstr/strcpy/strpbrk的函数
- 第五章、寻找满足条件的两个或多个数
- 第六章、求解500万以内的亲和数
- 第七章、求连续子数组的最大和
- 第八章、从头至尾漫谈虚函数
- 第九章、闲话链表追赶问题
- 第十章、如何给10^7个数据量的磁盘文件排序
- 第十一章、最长公共子序列(LCS)问题
- 第十二~十五章:数的判断,中签概率,IP访问次数,回文问题(初稿)
- 第二十六章:基于给定的文档生成倒排索引的编码与实践
- 第二十七章:不改变正负数之间相对顺序重新排列数组
- 第二十八~二十九章:最大连续乘积子串、字符串编辑距离
- 第三十~三十一章:字符串转换成整数,字符串匹配问题
- 第三十二~三十三章:最小操作数,木块砌墙问题
- 第三十四~三十五章:格子取数问题,完美洗牌算法
- 第三十六~三十七章、搜索智能提示suggestion,附近地点搜索
- 第三十八章:Hero在线编程判题、出题系统的演进与优化
- 第三十九~四十章:最近公共祖先LCA问题、打印螺旋矩阵
- 第四十一章~四十二章:荷兰国旗、矩阵相乘Strassen算法
- ...
程序员编程艺术第1~37章带标签的最新PDF下载地址为(3天3000人下载):http://download.csdn.net/detail/v_july_v/6694053。
编程艺术github优化版阅读地址:https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/Readme.md。
重大消息:经过反复修改、优化,编程艺术系列最终成书出版,并改名为《编程之法:面试和算法心得》,目前京东、当当、亚马逊等各大网店均已有现货销售。京东抢购地址:http://item.jd.com/11786791.html。
四、红黑树、B树、R树、Trie树
- 教你初步了解红黑树 (红黑树系列)
- 红黑树算法的实现与剖析
- 红黑树的C实现完整源码
- 一步一图一代码,R-B Tree
- 红黑树插入和删除结点的全程演示
- 红黑树的C++完整实现源码
- 从2-3-4树谈到Red-Black Tree(红黑树)
- 从B树、B+树、B*树谈到R 树 (B树的PDF)
- B树的C 实现
- 从Trie树(字典树)谈到后缀树 (其余树结构)
- 从LSM-Tree、COLA-Tree谈到StackOverflow、OSQA
-
5.1 AI数学基础
- 数据挖掘中所需的概率论与数理统计知识、上
- 一文通透优化算法:从随机梯度、随机梯度下降法到牛顿法、共轭梯度
- 5.2 AI经典模型
- 数据挖掘领域十大经典算法初探
- 从K近邻算法、距离度量谈到KD树、SIFT+BBF算法
- 从决策树学习谈到贝叶斯分类算法、EM、HMM
- 支持向量机通俗导论(理解SVM的三层境界) PDF下载 LaTeX版本1 LaTeX版本2
- 最大熵模型中的数学推导
- 如何通俗理解EM算法
- Adaboost 的原理与推导 LaTeX版本下载
- 从拉普拉斯矩阵说到谱聚类
- 从贝叶斯方法谈到贝叶斯网络 LaTeX版本下载
- 通俗理解LDA主题模型 LaTeX版本下载
- CNN笔记:通俗理解卷积神经网络
- 图解CNN:通过100张图一步步理解CNN
- 一文读懂目标检测:R-CNN、Fast R-CNN、Faster R-CNN、YOLO、SSD
- 通俗理解kaggle比赛大杀器xgboost
- 如何从RNN起步,一步一步通俗理解LSTM
- 如何通俗理解word2vec
- ..
- 5.3 AI工程实践
- 一文读懂特征工程
- 教你从头到尾利用DL学梵高作画:GTX 1070 cuda 8.0 tensorflow gpu版
- 没GPU也能玩梵高作画:Ubuntu tensorflow CPU版
- 基于torch学汪峰写歌词、聊天机器人、图像着色/生成、看图说话、字幕生成
- 教你从头到尾利用DQN自动玩flappy bird(全程命令提示,GPU+CPU版)
- 手把手教你搭建caffe及手写数字识别(Ubuntu下且附mac、纯通俗教程)
- 如何从零起步学习AI(附学习路线)
- GAN之父在NIPS 2016上做的报告:两个竞争网络的对抗(含译文下载)
- Kaggle—So Easy!百行代码实现排名Top 5%的图像分类比赛
- BAT机器学习面试1000题系列(第1~500题)
六、其它重要文章节选
-
6.1、经典数据结构 & 算法系列:
- 6.4、推荐 & 搜索算法系列:
- 细数二十世纪最伟大的10大算法
- 当今世界最为经典的十大算法--投票进行时 (本blog将评选出当今世界最为经典的十大算法)
- 推荐引擎算法学习导论
- 搜索引擎技术之概要预览
- Machine Learning读书会,面试算法讲座,创业活动,算法班(14年10月) (含所有线下讲座PPT 集锦)
- 三五杆枪,可干革命,三五个人,可以创业
- 结构之法算法之道blog博文集锦第6、第7期CHM文件 第8期 第9期下载(第9期截止到2014年12月9日)
- ....
后记
世上本无路,走的人多了,也就成了路。世上本无免费的午餐,分享的人多了,也就造就了开源的辉煌。如果你发现了本blog中的任何一个错误,漏洞,bug,和问题,请一定不吝指正,thanks。此外,你可以永久通过搜索引擎搜索本博客名称的前4个字,即:“结构之法” 这4个关键字,进入本博客。
最后,感谢CSDN,感谢所有一直以来关注本blog的所有朋友。谢谢大家,谢谢。
转发送书
欢迎大家转发下条微博:http://weibo.com/1580904460/zqzTgyAW3,我会不定期抽奖,经典IT图书大赠送(同时,下面个人最喜欢的三篇文章已收录到今2015年10月14日上市销售的我的新书《编程之法:面试和算法心得》中:http://item.jd.com/11786791.html):
2015年,July团队正式创业,上半年推出在线教育网站:https://www.julyedu.com/category/index(面试、算法、机器学习在线课程)。July、二零一五年九月十五日。
另,我的新书《编程之法:面试和算法心得》终于在2015年10月14日上架开卖了!京东抢购地址:http://item.jd.com/11786791.html。目前,京东、当当、亚马逊等各大网店均已有现货销售。
-
(算法)通俗易懂的字符串匹配KMP算法及求next值算法
2018-10-06 00:23:54大多数据结构课本中,串涉及的内容即串的模式匹配,需要掌握的是朴素算法、KMP算法及next值的求法。在考研备考中,参考严奶奶的教材,我也是在关于求next值的算法中卡了一下午时间,感觉挺有意思的,把一些思考的...大多数据结构课本中,串涉及的内容即串的模式匹配,需要掌握的是朴素算法、KMP算法及next值的求法。在考研备考中,参考严奶奶的教材,我也是在关于求next值的算法中卡了一下午时间,感觉挺有意思的,把一些思考的结果整理出来,与大家一起探讨。
本文的逻辑顺序为
1、最基本的朴素算法
2、优化的KMP算法
3、应算法需要定义的next值
4、手动写出较短串的next值的方法
5、最难理解的、足足有5行的代码的求next值的算法
所有铺垫为了最后的第5点,我觉得以这个逻辑下来,由果索因还是相对好理解的,下面写的很通俗,略显不专业…一、问题描述
给定一个主串S及一个模式串P,判断模式串是否为主串的子串;若是,返回匹配的第一个元素的位置(序号从1开始),否则返回0;如S=“abcd”,P=“bcd”,则返回2;S=“abcd”,P=“acb”,返回0。
二、朴素算法
最简单的方法及一次遍历S与P。以S=“abcabaaaabaaacac”,P="abaabcac"为例,一张动图模拟朴素算法:
这个算法简单,不多说,附上代码#include<stdio.h> int Index_1(char s[],int sLen,char p[],int pLen){//s为主串,sLen为主串元素个数,p为模式串,pLen为模式串的个数 if(sLen<pLen)return 0; int i = 1,j = 1; while(i<=sLen && j<=pLen){ if(s[i]==p[j]){i++;j++;} else{ i = i-j+2; j = 1; } } if(j>pLen) return i-pLen; return 0; } void main(){ char s[]={' ','a','b','c','a','b','a','a','a','a','b','a','a','b','c','a','c'};//从序号1开始存 char p[]={' ','a','b','a','a','b','c','a','c'}; int sLen = sizeof(s)/sizeof(char)-1; int pLen = sizeof(p)/sizeof(char)-1; printf("%d",Index_1(s,sLen,p,pLen)); }
三、改进的算法——KMP算法
朴素算法理解简单,但两个串都有依次遍历,时间复杂度为O(n*m),效率不高。由此有了KMP算法。
一般的,在一次匹配中,我们是不知道主串的内容的,而模式串是我们自己定义的。
朴素算法中,P的第j位失配,默认的把P串后移一位。
但在前一轮的比较中,我们已经知道了P的前(j-1)位与S中间对应的某(j-1)个元素已经匹配成功了。这就意味着,在一轮的尝试匹配中,我们get到了主串的部分内容,我们能否利用这些内容,让P多移几位(我认为这就是KMP算法最根本的东西),减少遍历的趟数呢?答案是肯定的。再看下面改进后的动图:
这个模拟过程即KMP算法,若没有看明白,继续往下看相应的解释,理解需要把P多移几位,然后回头再看一遍这个图就很明了了。
相比朴素算法:
朴素算法: 每次失配,S串的索引i定位的本次尝试匹配的第一个字符的后一个。P串的索引j定位到1;T(n)=O(n*m)
KMP算法: 每次失配,S串的索引i不动,P串的索引j定位到某个数。T(n)=O(n+m),时间效率明显提高而这“定位到某个数”,这个数就是接下来引入的next值。(实际上也就是P往后移多少位,换一种说法罢了:从上图中也可以看出,失配时固定i不变,令S[i]与P[某个数]对齐,实际上是P右移几位的另一种表达,只有为什么这么表达,当然是因为程序好写。)
开——始——划——重——点!(图对逻辑关系比较好理解,但i和j的关系对后面求next的算法好理解!)
-
比如,Pj处失配,绿色的是Pj,则我们可以确定P1…Pj-1是与Si…Si+j-2相对应的位置一一相等的
-
假设P1…Pj-1中,P1…Pk-1与Pj-k+1…Pj-1是一一相等的,为了下面说的清楚,我们把这种关系叫做“首尾重合”
-
那么可以推出,P1…Pk-1与Si…Si+j-2
-
显然,接下来要做的就是把模式串右移了,移到哪里就不用多说了:
-
为了表示下一轮比较j定位的地方,我们将其定义为next[j],next[j]就是第j个元素前j-1个元素首尾重合部分个数加一,当然,为了能遍历完整,首尾重合部分的元素个数应取到最多,即next[j]应取尽量大的值,原因挺好理解的,可以想个例子模拟一下,会完美跳过正确结果。在上图中就是绿色元素的next值为蓝色元素的序号。也即,对于字符串P,next[8]=4。如此,再看一下上面的动图是不是清楚了不少。
-
最后,如果我们知道了一个字符串的next值,那么KMP算法也就很好懂了。相比朴素算法,当发生失配时,i不变,j=next[j]就好啦!接下来就是怎么确定next值了。
四、手动写出一个串的next值
我们规定任何一个串,next[1]=0。(不用next[0],与串的所有对应),仍是一张动图搞定问题:
这个扫一眼就能依次写出,会了这个方法,应付个期末考试没问题了。通过把next值“看”出来,我们再来分析next值,这就很容易得到超级有名的公式了,这个式子对后面的算法理解很重要!所以先要看懂这个式子,如果上面的内容通下来了,这个应该很容易看懂了:
五、求next的算法
终于到了最后了~短的串的next值我们可以“看”出来,但长的串就需要借助程序了,具体算法刚接触的时候确实不容易理解,但给我的体验,把上面的内容写完,现在感觉简简单单了…先附上程序再做解释,(终于到了传说中的整整5行代码让我整理了一下午)。
int GetNext(char ch[],int cLen,int next[]){//cLen为串ch的长度 next[1] = 0; int i = 1,j = 0; while(i<=cLen){ if(j==0||ch[i]==ch[j]) next[++i] = ++j; else j = next[j]; } }
-
还是先由一般再推优化:
直接求next[j+1](至于为什么是j+1,是为了和下面的对应)
根据之前的分析,next[j+1]的值为pj+1的前j个元素的收尾重合的最大个数加一。即需要满足两个条件,把它的值一步步“检验”出来。一是“个数最多”的,因此要从可能的最大值开始验;二是“首尾重合”,因此要一一对应验是否相等。
不难理解,next[j+1]的最大值为j,所有我们从next[j+1]=j开始“验证”。有以下优先判断顺序:
if(P1…Pj-1 == P2…Pj) => next[j+1]=j
else if(P1…Pj-2 == P3…Pj) =>next[j+1]=j-1
else if(P1…Pj-3 == P4…Pj) =>next[j+1]=j-2
…
…
…
else if(P1P2 == Pj-1Pj) => next[j+1]=3
else if(P1 == Pj-1) => next[j+1]=2
else if(P1 != Pj-1) => next[j+1]=1
每次前去尾1个,后掐头1个,直至得到next[j+1] -
再进一步想,next值是一个“工具”,我们单独的求next[j+1]是完全没有意义的,就是说要求next就要把所有j的next求出来。所有一般的,我们都是已知前j个元素的next值,求next[j+1],以此递推下去,求完整的next数组。
但是,上面的思考过程还是最根本的。所以问题变为两个:知道前j个元素的next的情况下,
①next[j+1]的可能的最大值是多少(即从哪开始验证)
②某一步验证失败后,需要“前去尾几个,后掐头几个?”(即本次验证失败后,再验证哪个值)
看一下的分析:
1、next[j+1]的最大值为next[j]+1。
因为:
假设next[j]=k1,则可以说明P1…Pk1-1=Pj-k1+1…Pj-1,且这是前j个元素最大的首尾重合序列。
如果Pk1=Pj,那么P1…Pk1-1PK=Pj-k1+1…Pj-1Pj,那么k+1这也是前j+1个元素的最大首尾重合序列,也即next[j+1]的值为k1+1
2、如果Pk1≠Pj,那么next[j+1]可能的次大值为next[next[j]]+1,以此类推即可高效求出next[j+1]
这里不好解释,直接看下面的流程分析及图解开——始——划——重——点!
从头走一遍流程
①求next[j+1],设值为m
②已知next[j]=k1,则有P1…Pk1-1 = Pj-k1+1…Pj-1
③如果Pk1=Pj,则P1…Pk1-1PK = Pj-k1+1…Pj-1Pj,则next[j+1]=k1+1,否则
④已知next[k1]=k2,则有P1…Pk2-1 = Pk1-k2+1…Pk1-1
⑤第二第三步联合得到:
P1…Pk2-1 = Pk1-k2+1…Pk1-1 = Pj-k1+1…Pk2-k1+j-1 = Pj-k2+1…Pj-1 即四段重合
⑥这时候,再判断如果Pk2=Pj,则P1…Pk2-1P~k2 = Pj-k2+1…Pj-1Pj,则next[j+1]=k2+1;否则再取next[k2]=k3…以此类推上面几步,耐心看下来,结合那个式子很容易看懂。最后,再加一个图的模拟帮助理解:
1、要求next[k+1] 其中k+1=17
2、已知next[16]=8,则元素有以下关系:
3、如果P8=P16,则明显next[17]=8+1=9
4、如果不相等,又若next[8]=4,则有以下关系
又加上2的条件知
主要是为了证明:
5、现在在判断,如果P16=P4则next[17]=4+1=5,否则,在继续递推
6、若next[4]=2,则有以下关系
7、若P16=P2,则next[17]=2+1=3;否则继续取next[2]=1、next[1]=0;遇到0时还没出结果,则递推结束,此时next[17]=1。最后,再返回看那5行算法,应该很容易明白了! -
-
经典算法(5)杨辉三角
2019-11-04 17:15:35杨辉三角 是经典算法,这篇博客对它的算法思想进行了讲解,并有完整的代码实现。 -
2020最新-精选基础算法100题(面试必备)
2020-05-18 19:58:16作为一个程序员,算法能力必不可少,虽然不一定是算法工程师,但是算法还是彰显着个人的编码能力,面试中也经常会被问到,甚至会被要求临场做算法题,所以,还是好好积累吧。 个人其实对算法挺有兴趣的,从3月份... -
雪花算法的原理和实现Java
2019-05-05 15:05:24SnowFlake 算法,是 Twitter 开源的分布式 id 生成算法。其核心思想就是:使用一个 64 bit 的 long 型的数字作为全局唯一 id。在分布式系统中的应用十分广泛,且ID 引入了时间戳,基本上保持自增的。 这 64 个 ... -
10大经典排序算法动画解析-收藏
2018-12-13 14:13:07排序算法是《数据结构与算法》中最基本的算法之一。 排序算法可以分为内部排序和外部排序。 内部排序是数据记录在内存中进行排序。 而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要... -
夜深人静写算法(二)- 动态规划
2017-12-28 14:57:36动态规划入门:初学者 -
夜深人静写算法(一)- 搜索入门
2017-12-28 14:43:02搜索入门:深度优先搜索(记忆化、剪枝、IDA*)、广度优先搜索(A*、双向广搜) -
粒子群优化算法(PSO)
2018-06-04 20:07:09粒子群优化算法(Partical Swarm Optimization PSO),粒子群中的每一个粒子都代表一个问题的可能解,通过粒子个体的简单行为,群体内的信息交互实现问题求解的智能性。由于PSO操作简单、收敛速度快,... -
Dijkstra算法原理
2017-02-19 22:46:13Dijkstra算法 1.定义概览 Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法是很有代表性... -
JAVA近百种算法大全
2013-05-29 10:25:35最近找到的JAVA近百种算法大全 分享一下 java算法大全,有近100多种常见算法的源代码,是学习JAVA算法的难得资料,需要的童鞋来下载吧! -
防劝退!数据结构和算法难理解?可视化动画带你轻松透彻理解!
2019-11-22 13:50:09大家好,我是 Rocky0429,一个连数据结构和算法都不会的蒟蒻… 学过数据结构和算法的都知道这玩意儿不好学,没学过的经常听到这样的说法还没学就觉得难,其实难吗?真难! 难在哪呢?当年我还是个小蒟蒻,初学数据... -
各种聚类算法(原理+代码+对比分析)最全总结
2017-12-14 10:41:20序言 还是要持续总结,持续积累。 一、聚类的目标 使同一类对象的相似度尽可能地大;不同类对象之间的相似度尽可能地小。 二、聚类算法分类 ...算法:K-MEANS算法、K-MEDOIDS算法、CLARANS算法 2.... -
计算机操作系统_银行家算法
2018-12-05 23:21:02银行家算法 -
页面置换算法-CLOCK置换算法及其改进版算法
2018-12-29 13:31:51页面置换算法中的LRU算法最接近理想情况下的OPT算法,但是实现起来比较困难且开销较大,所以很多设计者试图用开销比较小的算法接近LRU算法,CLOCK算法就是其中一种。 1.简单的CLOCK算法是通过给每一个访问的页面... -
最优化算法之粒子群算法(PSO)
2018-08-03 10:26:45一、粒子群算法的概念 粒子群优化算法(PSO:Particle swarm optimization) 是一种进化计算技术(evolutionary computation)。源于对鸟群捕食的行为研究。粒子群优化算法的基本思想:是通过群体中个体之间的... -
算法和算法评价
2019-07-05 20:42:11一、算法的基本概念 算法是对特定问题求解步骤的一种描述,它是指令的有限序列,其中的每条指令表示一个或多个操作。具有以下性质: 1.有穷性:一个算法必须总是在执行有穷步之后结束,且每一步都可在有穷时间内... -
神经网络BP反向传播算法原理和详细推导流程
2018-05-09 22:25:531 反向传播算法和BP网络简介 误差反向传播算法简称反向传播算法(即BP算法)。使用反向传播算法的多层感知器又称为BP神经网络。BP算法是一个迭代算法,它的基本思想为:(1)先计算每一层的状态和激活值,直到最后一... -
Dijkstra算法图文详解
2018-11-20 09:19:59Dijkstra算法 Dijkstra算法算是贪心思想实现的,首先把起点到所有点的距离存下来找个最短的,然后松弛一次再找出最短的,所谓的松弛操作就是,遍历一遍看通过刚刚找到的距离最短的点作为中转站会不会更近,如果... -
算法的时间与空间复杂度(一看就懂)
2018-11-21 11:17:45算法(Algorithm)是指用来操作数据、解决程序问题的一组方法。对于同一个问题,使用不同的算法,也许最终得到的结果是一样的,但在过程中消耗的资源和时间却会有很大的区别。 那么我们应该如何去衡量不同算法之间... -
简单易懂——Dijkstra算法讲解
2018-02-18 00:22:46我的机器学习教程「美团」算法工程师带你入门机器学习 已经开始更新了,欢迎大家订阅~ 任何关于算法、编程、AI行业知识或博客内容的问题,可以随时扫码关注公众号「图灵的猫」,加入”学习小组“,沙雕博主在线答疑... -
数据挖掘算法——常用分类算法总结
2019-06-17 10:55:22常用分类算法总结分类算法总结NBC算法LR算法SVM算法ID3算法C4.5 算法C5.0算法KNN 算法ANN 算法 分类算法总结 分类是在一群已经知道类别标号的样本中,训练一种分类器,让其能够对某种未知的样本进行分类。分类算法... -
快速排序算法
2019-01-11 21:09:08但是这种算法时间复杂度高,当需要排序的元素较多时,程序运行时间很长,因此产生了快速排序算法。该算法的实现可分为以下几步: 1. 在数组中选一个基准数(通常为数组第一个); 2. 将数组中小于基准数的数据移到... -
经典算法书籍推荐以及算法书排行【算法四库全书】
2019-05-05 20:14:35经典算法书籍推荐以及算法书排行【算法四库全书】 作者:霞落满天 https://linuxstyle.blog.csdn.net/ https://blog.csdn.net/21aspnet 行文方式:类似《四库全书》截取经典算法书目录和精华篇章 版权说明:本文... -
页面置换算法
2017-07-01 20:10:50本实验的目的是通过请求页式存储管理中页面置换算法模拟设计,了解虚拟存储技术的技术特点,掌握请求页式存储管理的页面置换算法。 2. 实验内容 (1)设置一个页面走向序列。 (2)计算并输出下述各种算法在不同... -
详解遗传算法(含MATLAB代码)
2019-05-29 11:30:47一、遗传算法概述 二、遗传算法的特点和应用 三、遗传算法的基本流程及实现技术 3.1 遗传算法的基本流程 3.2 遗传算法的实现技术 1.编码 2.适应度函数 3.选择算子 4.交叉算子 5.变异算子 6.运行参数 四、... -
算法面试题汇总 leetcode
2020-09-23 23:22:13算法面试题汇总 leetcode -
聚类算法-最大最小距离算法(实例+代码)
2016-12-17 17:35:13聚类算法-最大最小距离算法(实例+代码) 【尊重原创,转载请注明出处】http://blog.csdn.net/guyuealian/article/details/53708042 目录 聚类算法-最大最小距离算法(实例+代码) 一、最大最小距离算法基本思想 ...
-
微服务系列第七十一季-Introducing Spring Boot
-
小白自学Photoshop美工人像抠图平面设计全套教程
-
mysql-installer-5.5.23.0.msi
-
搭建Pytorch深度学习框架所需资源包,无需再下载任何依赖包
-
marc大文件查看及检索-PxMarcBigFileView_0.3
-
国家注册信息安全工程师体系课程(CISP-PTE)
-
21年新接口自动化测试视频postman教程 零基础接口测试
-
(新)备战2021软考网络工程师终极解密培训套餐
-
GitHub的使用
-
C#文件传输、Socket通信、大文件断点续传
-
基于Vue3.0结合Vuetify组件开发的网易云案例(粉丝可以免费下载,私聊我)
-
彻底学会正则表达式
-
【数据分析-随到随学】互联网行业业务指标及行业数
-
Windows下或Centos下根据pid查找应用路径
-
MySQL存储引擎--MySAM和InnoDB对比
-
被跟卖会有什么结果?
-
安卓P Q R ,remount的脚本
-
一阶数字锁相环设计simulink仿真
-
TPS54160开关电源原理图及PCB
-
(新)备战2021软考网络工程师培训学习套餐