KMP算法的最佳和最差时间复杂度是多少
What is the best & worst time complexity Of KMP algorithm
需要说明KMP算法的最佳时间复杂度和最差时间复杂度。令我困惑的是 O(n) 的最差搜索时间复杂度。网上看的明白是有两个索引。一个索引 i 用于文本，另一个索引 j 用于模式。而且我们不减少文本索引 i。但是当存在不匹配且 j 值大于 0 时，我们会减少模式索引 j。在这种情况下，i 保持不变。那么最坏时间复杂度怎么可能是O(n)呢？它应该比 O(mn) 多。对于特定的 i 值，我们可以对 j 进行多次迭代。
最好的情况是什么？它与最坏情况有什么不同？我正在寻找简单的解释，因为我已经完成了不同的教程。
KMP 不会在不增加 i 的情况下增加 j。因此，即使在 i 的每次增量之间可以有 j 的 Theta(m) 次减量，在算法过程中 j 的减量总数不能超过 j 的增量总数，它等于增量数我的。都是 Theta(n)，KMP 的最差 best-case 渐近 运行 时间（假设我们找到所有匹配；如果没有，那么显然最好的情况是 Theta(m)）。
大卫的回答是正确的。您需要先匹配 j 。然后 j 值将增加并变得大于零。之后你可以减少 j 值。
当你递增 j 时，你也在递增 i。因此，如果您将 j index 递减 n 次，这意味着您至少已经将 j index 递增了 n 次，这反过来又意味着您已经将 i index 递增了 n 次。这样你就完成了对文本的遍历。
因此时间复杂度为 n 个负步 + n 个正步 = 2n 个步。那就是 O(n).
您可以查看此 link http://www.w3spot.com/2020/07/kmp-algorithm-explained-in-plain-english.html，它通过几个示例逐步解释了它，一个具有重复模式，一个具有 non-repetitive 模式。而且简单易懂。
假设我们在字符串s中搜索字符串p，每个字符串的长度为m和n。
最好的例子，显然是 O(m)
但是如果p不在s中，最好的情况应该是，p一旦不匹配就尽可能右移，搜索阶段的开销为O(n + n/m).
最坏的例子，一旦不匹配，p就非常保守地右移，
搜索阶段花费 O(n + (m-1) * (n/m)).
其中 n/m 是有多少不匹配。
而且，加上预处理阶段，在最好和最坏的情况下，总时间成本仍然是 O(m+n)。
需要说明KMP算法的最佳时间复杂度和最差时间复杂度。令我困惑的是 O(n) 的最差搜索时间复杂度。网上看的明白是有两个索引。一个索引 i 用于文本，另一个索引 j 用于模式。而且我们不减少文本索引 i。但是当存在不匹配且 j 值大于 0 时，我们会减少模式索引 j。在这种情况下，i 保持不变。那么最坏时间复杂度怎么可能是O(n)呢？它应该比 O(mn) 多。对于特定的 i 值，我们可以对 j 进行多次迭代。
最好的情况是什么？它与最坏情况有什么不同？我正在寻找简单的解释，因为我已经完成了不同的教程。
KMP 不会在不增加 i 的情况下增加 j。因此，即使在 i 的每次增量之间可以有 j 的 Theta(m) 次减量，在算法过程中 j 的减量总数不能超过 j 的增量总数，它等于增量数我的。都是 Theta(n)，KMP 的最差 best-case 渐近 运行 时间（假设我们找到所有匹配；如果没有，那么显然最好的情况是 Theta(m)）。
大卫的回答是正确的。您需要先匹配 j 。然后 j 值将增加并变得大于零。之后你可以减少 j 值。 当你递增 j 时，你也在递增 i。因此，如果您将 j index 递减 n 次，这意味着您至少已经将 j index 递增了 n 次，这反过来又意味着您已经将 i index 递增了 n 次。这样你就完成了对文本的遍历。
因此时间复杂度为 n 个负步 + n 个正步 = 2n 个步。那就是 O(n).
您可以查看此 link http://www.w3spot.com/2020/07/kmp-algorithm-explained-in-plain-english.html，它通过几个示例逐步解释了它，一个具有重复模式，一个具有 non-repetitive 模式。而且简单易懂。
假设我们在字符串s中搜索字符串p，每个字符串的长度为m和n。
最好的例子，显然是 O(m)
但是如果p不在s中，最好的情况应该是，p一旦不匹配就尽可能右移，搜索阶段的开销为O(n + n/m).
最坏的例子，一旦不匹配，p就非常保守地右移， 搜索阶段花费 O(n + (m-1) * (n/m)).
其中 n/m 是有多少不匹配。
而且，加上预处理阶段，在最好和最坏的情况下，总时间成本仍然是 O(m+n)。