×

数据结构与算法分析 算法 数据结构

什么是数据结构和算法分析在编程里起到什么作用?KMP模式匹配算法是什么

admin admin 发表于2022-06-27 15:53:19 浏览107 评论0

抢沙发发表评论

什么是数据结构和算法分析在编程里起到什么作用


编程是为了解决问题,这些问题并表都是数值计算,其所处理的数据并不都是数值,但计算机所能处理的最终是0和1的二进制串,所以需要把问题中的数据用计算机能处理的方式来表示,这就需要数据结构。

简单的说,数据结构是数据在计算机中的表示方式,有逻辑结构和物理结构之分,如逻辑上同样的队列,物理上可以是顺序存储,也可以是链式存储。

通俗的讲,算法就是解决问题的方法,比如同样的排序,可以用冒泡排序、插入排序等,不同的算法可以达到相同的目标,但是效率可能有所不同。

KMP模式匹配算法是什么


KMP模式匹配算法是一种改进算法,是由D.E.Knuth、J.H.Morris和v.R.Pratt提出来的,因此人们称它为“克努特-莫里斯-普拉特操作”,简称KMP算法。此算法可以在O(n+m)的时间数量级上完成串的模式匹配操作。其改进在于:每当一趟匹配过程出现字符不相等时,主串指针i不用回溯,而是利用已经得到的“部分匹配”结果,将模式串的指针j向右“滑动”尽可能远的一段距离后,继续进行比较。

1.KMP模式匹配算法分析回顾图4-5所示的匹配过程示例,在第三趟匹配中,当i=7、j=5字符比较不等时,又从i=4、j=1重新开始比较。然而,经仔细观察发现,i=4和j=1、i=5和j=1以及i=6和j=1这三次比较都是不必进行的。因为从第三趟部分匹配的结果就可得出,主串中的第4、5和6个字符必然是b、c和a(即模式串第2、第2和第4个字符)。因为模式中的第一个字符是a,因此它无须再和这三个字符进行比较,而仅需将模式向右滑动2个字符的位置进行i=7、j=2时的字符比较即可。同理,在第一趟匹配中出现字符不等时,仅需将模式串向右移动两个字符的位置继续进行i=2、j=1时的字符比较。由此,在整个匹配过程中,i指针没有回溯,如图1所示。-数据结构

图1改进算法的模式匹配过程示意


深度学习中经常提到的神经网络是什么


介绍深度学习就必须要介绍神经网络,因为深度学习是基于神经网络算法的,其实最开始只有神经网络算法,上文也提到2006年Geoffrey Hinton老爷子提出了Deep Learning,核心还是人工神经网络算法,换了一个新的叫法,最基本的算法没有变。
通过神经元接收外界信号,达到一定阈值,触发动作电位,通过突触释放神经递质,可以是兴奋或抑制,影响突触后神经元。通过此实现大脑的计算、记忆、逻辑处理等,进行做出一系列行为等。同时不断地在不同神经元之间构建新的突触连接和对现有突触进行改造,来进行调整。有时候不得不感叹大自然的鬼斧神工,900亿神经元组成的神经网络可以让大脑实现如此复杂的计算和逻辑处理。
-算法