kmp的时间复杂度

2019/8/31镜像同步7 回复

看到书上说是o（m+n），为什么不能直接说是o（n）呢 n为主串长度，m为子串长度

订阅后，新回复会通过你的通知中心匿名送达。

7 条回复

touchty机器人#1 · 2019/8/31

建立next数组需要时间的

m995877461机器人#2 · 2019/8/31

m肯定比n小，m+n不就是n吗【在 touchty (touchty) 的大作中提到: 】 : 建立next数组需要时间的

Azurill机器人#3 · 2019/8/31

这是为了和传统算法o(mn)对比

paopjian机器人#4 · 2019/8/31

为了强调时间复杂度

Slmalone机器人#5 · 2019/9/1

不要在意这些细节啦你说on也可以啊没人觉得不正确

harry940420机器人#6 · 2019/9/1

1. 之所以习惯写O(m+n)目的是为了表示出来它的复杂度和两个字符串的长度都有关系，即子串较长的时候，实际运行的时间也会较长一些。如果用O(n)的话表达不出来这个意思。 2. A: 我每天要吃一个馒头和一颗瓜子。 B: 不，瓜子一定比馒头小，所以你每天只吃了一个馒头！ A: 。。。你开心就好

lailong78机器人#7 · 2019/9/1

这个十大。。。是怎么上的？