KMP算法的最佳和最差时间复杂度是多少

Question

需要澄清KMP算法的最佳时间复杂度和最差时间复杂度。让我感到困惑的是最差的搜索时间复杂度为 O(n)。网上看了一下明白是有两个索引。一个索引 i 用于文本，另一个索引 j 用于模式。并且我们不会递减文本索引 i。但当存在不匹配且 j 值大于 0 时，我们会递减模式索引 j。在这种情况下，i 保持不变。那么最坏时间复杂度怎么可能是O(n)呢？应该比 O(mn) 还要多。对于 i 的特定值，我们可以对 j 进行多次迭代。

最好的情况是什么？这与最坏的情况有什么不同吗？我正在寻找简单的解释，因为我已经完成了不同的教程。

Answer 1

大卫的回答是正确的。你需要先匹配j。然后 j 值将增加并变得大于零。之后您可以减少 j 值。当你增加 j 时，你也增加了 i。因此，如果您将 j 索引递减 n 次，则意味着您至少已经将 j 索引递增了 n 次，而这又意味着您已经将 i 索引递增了 n 次。这样你就完成了文本的遍历。

因此时间复杂度为 n 个负步骤 + n 个正步骤 = 2n 个步骤。那就是 O(n)。

您可以查看此链接http://www.w3spot.com/2020/07/kmp-algorithm-explained-in-plain-english.html，其中通过几个示例逐步解释了这一点，一个具有重复模式，一个具有重复模式具有不重复的模式。而且它很简单易懂。

Answer 2

KMP 永远不会在不增加 i 的情况下增加 j。因此，即使 i 的每次增量之间可能存在 j 的 Theta(m) 递减，但在算法过程中 j 的递减总数不能超过 j 的增量总数，即等于增量数岛的 全部都是 Theta(n)，KMP 最坏和最好情况的渐近运行时间（假设我们找到所有匹配；如果没有，那么显然最好的情况是 Theta(m)）。