数据结构(邓俊辉)学习笔记】串 07——KMP算法:分摊分析

2024-08-28 03:20

本文主要是介绍数据结构(邓俊辉)学习笔记】串 07——KMP算法:分摊分析,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 1.失之粗糙
  • 2.精准估计

1.失之粗糙

以下,就来对 KMP 算法的性能做一分析。我们知道 KMP 算法的计算过程可以根据对齐位置相应的分为若干个阶段,然而每一个阶段所对应的计算量是有很大区别的。很快就会看到,如果只是简单地从最坏的角度来进行估计,我们将无法准确地来评估这种算法,而实际上真正有效的方法是,放眼整个计算过程,将整体的计算成本分摊到每一个阶段。

没错,分摊。我们这里需要再一次地借助分摊的分析技巧,而这里我们将要采用的估算方法也是分拆分析中的一种典型手法。

我们首先来看一种貌似无可厚非,但实则非常粗糙的估算方法。
在这里插入图片描述

这一方法建议我们将注意力放在文本串中的任意字符上,因为这种方法认为,我们只要估算出每一个字符所参与的比对次数,也自然地就可以得到整体的比对次数。然而我们很快就会发现,在任何一个特定的字符处,我们的模式串的确有可能会多次地后移。实际上不能构造出这样的例子,也就是相对于文本串中的某个特定字符,模式串有可能需要连续的后移多次,并且用其中多答 Ω(m) 个字符,与文本串中的这个字符进行比对。当然具体的次数可能是m/3、m/40 或者m/500。但无论如何,在渐进的意义上,都可以达到Ω(m)次。因此,如果再考虑到主串所贡献的那个因子 n,那么按照这种思路,KMP 的时间复杂度似乎会高达Ω(n*m)。

这样一个分析结论多少会让我们感到沮丧,因为蛮力算法也不过如此。然而事实上,这种方法的确实失之粗糙,而接下来更为精细地分析将表明,KMP 算法的效率即便在最坏情况下也不会超过线性O(n)。

2.精准估计

在这里插入图片描述为了对KMP算法性能作出更为精细的分析,我们可以参照在第一章就确立的方法,将这个算法中,不涉及到实质计算内容的非迭代部分都删除掉,而将注意力集中于复杂度的主体,也就是其中的这个循环。

在这里,我们需要引入一个观察量 k。 在算法执行过程中的任何时刻,这个 k 都等于 2*i - j。实际上,在很多开发环境中,都提供了观察功能,允许你设置这样一个表达式,并且在算法的调试运行过程中,动态地给出表达式所对应的数值。

实际上,随的算法中这个迭代过程的不断推进,这个观察变量 k, 必然是单调递增的。这一性质并不难看出,实际上无非 if 和 else 两种可能。

  1. 首先,如果当前这步迭代选取的是 if 分支,那么,根据算法的流程,i 和 j 会同步地递增一个单位。于是,作为 2*i - j,k 应该恰好增加一个单位。
  2. 反之,如果当前这步迭代进入的是 else 分支,那么尽管 i 不会受到任何影响,但是 j 会被替换为它对应的 next 表项,你应该记得我们此前已经指出, j 所对应的那个 next 表项必然会严格地小于 j。也就是说,经过这样一次替代之后,在数值上 j 必然会严格地减少,所以 k 也至少会增加一个单位。

综合这两种情况,我们就会发现 ,k 随着迭代的进行的确会严格单调地不断递增。

因此,整个计算过程中所进行的迭代步数就绝对不会超过 k。也就是说只要我们能够界定 k 的上界,也就自然确定了整个算法复杂度的上界。那么 k 的变化幅度究竟是多大呢?

  1. 首先,既然 i 和 j 的初值都是0,所以 k 的初值也应该是0。
  2. 而在算法结束时,i 至多与 n 同阶,而 j 也至少是一个常数。这也就意味着在渐进的意义上,k 绝对不会超过线性的范围。

至此,我们也就确凿地给出了 KMP 算法性能的一个准确估计。是的,这里给出的估计方法非常初等,因此其结论也毋庸置疑。

当然,作为进一步的探求,你或许会好奇于这里的 k,也就是 2*i - j 的具体含义,自行探索。

在这里插入图片描述

当然,作为 KMP 算法的有机组成部分,我们也不要忘了 next 表的构造过程。然而,正如我们已经看到的,这个预处理算法的原理及过程与主算法完全相同,因此其复杂度也应该线性正比于它自己的输入规模,也就是模式串的长度 O(m)。

这篇关于数据结构(邓俊辉)学习笔记】串 07——KMP算法:分摊分析的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1113580

相关文章

HarmonyOS学习(七)——UI(五)常用布局总结

自适应布局 1.1、线性布局(LinearLayout) 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列,Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距,达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式,且在各类尺寸屏幕上表现一致,其中交叉轴为垂直时,取值为Vert

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya(不是本人,claude AI)在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容: 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画(下)

【课程链接】 AntV G6:深入图形与图形分组、自定义节点、节点动画(下)_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中,应该怎样去计算和绘制图形,如何给一个图形制作不间断的动画,以及在鼠标事件之后产生动画。(有点难,需要好好理解) <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06

学习hash总结

2014/1/29/   最近刚开始学hash,名字很陌生,但是hash的思想却很熟悉,以前早就做过此类的题,但是不知道这就是hash思想而已,说白了hash就是一个映射,往往灵活利用数组的下标来实现算法,hash的作用:1、判重;2、统计次数;

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

性能分析之MySQL索引实战案例

文章目录 一、前言二、准备三、MySQL索引优化四、MySQL 索引知识回顾五、总结 一、前言 在上一讲性能工具之 JProfiler 简单登录案例分析实战中已经发现SQL没有建立索引问题,本文将一起从代码层去分析为什么没有建立索引? 开源ERP项目地址:https://gitee.com/jishenghua/JSH_ERP 二、准备 打开IDEA找到登录请求资源路径位置

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig