#串的简单模式匹配算法时间复杂度求解
#设主串长度为n 模式串为m
1.最坏时间复杂度是每个模式串都全部对比，并且遍历完整个主串，其结果为m*（n-m+1）即O（nm）
2.最好时间复杂度不应该是第一个子串就与模式串刚好匹配，返回值为1.
此时时间复杂度就是m，那不该是O（m）吗？为啥会是遍历完整个主串，结果是O（n）呢？不应该是O（m）<<O（n）吗？
求解答。
串的简单模式匹配算法时间复杂度求解
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
分享- 邀请回答
-
1条回答 默认 最新
於黾 2022-08-26 15:01关注你把整个题都理解偏了
模式匹配，不是查找子串
是主串必须整个能够匹配模式串才算匹配成功
你只比对前半串，不管后半串，你怎么知道后半串不会有匹配不上的字符解决 无用评论 打赏举报 分享
- 2021-09-02 08:02回答 1 已采纳 两层循环一般写O(n2) 递归没有循环O(n)
- 2022-05-18 12:57回答 1 已采纳 O（3n）= n
- 2023-01-22 20:07回答 2 已采纳 o（1/2）,1+2+3...，算出n*（n+1）/2,然后反解一下就得到执行的次数，即时间复杂度。
- 2022-11-13 00:33xw_lover的博客 串的模式匹配算法（简单模式匹配算法、KMP算法、next数组、KMP改进算法）
- 2021-09-17 14:24回答 1 已采纳 当n/(2^k) =1时，已经不能再进二分了，达到了递归退出条件i == j了，所以它的极限就是1
- 2021-10-06 19:54回答 1 已采纳 我用#CSDN#这个app发现了有技术含量的博客，小伙伴们求同去《时空复杂度（时间复杂度/空间复杂度）》, 一起来围观吧 时空复杂度（时间复杂度/空间复杂度）_LiuX
- 2022-07-22 14:02回答 1 已采纳 看看这个： 时间复杂度到底怎么算 https://baijiahao.b
- 2023-07-16 17:21DAY Ⅰ的博客 KMP算法就是消除指针i的回溯，让i指针只进不退，而只移动模式串指针指向位置的方法，由于此时"$p_1...p_{k-1}$"和"$p_{j-k+1}..p_j$"都是相同的，所以这时候相当于将$j1$指针指向前缀，$j1$不断前移，$j2$指针指向...
- 2023-04-12 20:32回答 1 已采纳 时间复杂度 O(log2n) 和 O(nlog2n) 都是表示算法的时间复杂度，但分别代表了不同的算法效率。其中，O(log2n) 表示算法的时间复杂度为对数级别，O(nlog2n) 表示算法的时间复
- 2023-04-19 21:40回答 2 已采纳 m+n和n其实都是O(n)
- 2021-09-08 18:32回答 1 已采纳 第一次i=0 j=0 j<i不成立循环0次第二次i=1 j=0 j<i成立循环1次。。。第n次循环n-11+2+..+n-1=(n*(n-1))/2复杂度O（n²）
- 2021-05-12 21:17青何的博客 这篇文章主要介绍了数据结构中的字符串以及有关字符串的很重要的算法——模式匹配算法，重点介绍了KMP算法的实现原理。
- 2022-04-12 19:17The..Fuir的博客 KMP模式匹配算法 简述 为了解决朴素模式匹配算法的低效 kmp模式匹配算法由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。KMP算法的核心是利用匹配失败后的...
- 2021-12-06 01:47Kevin_0629的博客 串的模式匹配算法暴力破解法原理伪代码KMP算法背景计算过程1号算法(Next数组)计算步骤KMP算法伪代码改进的KMP算法(NextVal数组)计算步骤改进KMP算法伪代码 暴力破解法 原理 通过已知的主串S和模式串T，进行匹配，...
- 2017-02-21 19:26Ouyang_Lianjun的博客 对于文本程序来说，找出一个子串在文本中的位置是特别重要的，我们称那个子串为模式串（pattern），然后我们称寻找的过程为：模式匹配（string match）。 2、实现算法（1）—朴素字符串匹配算法 原理：从
- 没有解决我的问题, 去提问
问题事件
创建了问题
8月26日
悬赏问题
- ¥15 Android Studio中如何把H5逻辑放在Assets 文件夹中以实现将h5代码打包为apk
- ¥15 使用小程序wx.createWebAudioContext()开发节拍器
- ¥15 关于#爬虫#的问题：请问HMDB代谢物爬虫的那个工具可以提供一下吗
- ¥15 vue3+electron打包获取本地视频属性，文件夹里面有ffprobe.exe 文件还会报错这是什么原因呢？
- ¥20 用51单片机控制急停。
- ¥15 孟德尔随机化结果不一致
- ¥15 在使用pyecharts时出现问题
- ¥15 深度学习残差模块模型
- ¥50 怎么判断同步时序逻辑电路和异步时序逻辑电路
- ¥15 差动电流二次谐波的含量Matlab计算