有人能给我解释一下Rabin-Karp算法的复杂度吗？

Question

我想了解为什么Rabin-Karp算法的最坏情况运行时间是O(nm)，而平均情况是O(n+m)。请有人帮助我吗？

- user6812711

---

这是一个重复的问题，与http://stackoverflow.com/questions/39054972/rabin-karp-algorithm-how-is-the-worst-case-omn-for-the-given-input相同，但SO不允许我使用该问题，因为答案既未被接受也未得到赞同。 - rici

Answer 1

维基百科 很好地解释了该算法的时间复杂度。

可以说，哈希计算函数 的有效性（指能够以恒定时间动态重复使用已计算的哈希值的能力）是算法时间复杂度计算中的一个决定性因素。

让我们看看哈希计算如何造成这种差异。

---

当以下情况时，时间复杂度为O(nm)：

call hash(s[1..m])                  // O(m) additive
for index from 1 to n-m+1           // O(n)
    //Code to check if substring matches
    call hash(s[index+1..index+m])  // Inefficient hash function, takes O(m), just like naive string matching

与 O(nm) 相比，相加的 O(m) 往往被大部分人忽略。

给定，O(m) + O(n)*O(m) = O(nm)

---

当：

时间复杂度为 O(n+m) 的情况下：

call hash(s[1..m])                  // O(m) additive
for index from 1 to n-m+1           // O(n)
    //Code to check if substring matches
    call hash(s[index+1..index+m])  //Efficient hash function which takes only O(1), applies Rolling Hashing

Giving, O(m) + O(n)*O(1) = O(m) + O(n) = O(m+n)

- Saurav Sahu

Answer 2

Rabin-Karp算法的最坏时间复杂度是O(nm)，因为它可能在每个点（有n个点）找到一个错误匹配，并且验证匹配需要最多m次比较，因为您需要实际比较字符串。

通过一个合理的哈希函数，这种情况不应该发生，但对于几乎任何哈希函数，都可以创建一个查询（即搜索的字符串和子字符串），展现上述病态行为。

因此，尽管R-K具有期望的时间复杂度为O(n)，但其最坏情况下的时间复杂度为O(nm)。（注意：由于m必须不大于n，因此n+m受2n限制，因此O(n+m)与O(n)相同。）

如果问题是查找所有匹配的子字符串，则更容易产生O(nm)行为，这是R-K经常使用的另一个环境。在这种情况下，在由n个 “a”组成的字符串中搜索由m个“a”组成的子字符串肯定需要nm时间，因为子字符串需要在源字符串的每个位置进行匹配。

还存在其他算法，可以在病态情况下仍然线性地找到所有子字符串。

- rici

---

谢谢你的帮助！现在我明白了这个算法最坏情况下的运行时间复杂度，但是我还不理解它的平均情况。能否请你再详细解释一下？ - user6812711

@user6812711：我描述的情况非常罕见。通常，几乎没有假阳性，而少数假阳性只需查看前一个或两个字符即可确定。因此，找到正确字符串所需的时间几乎总是O(n)，验证其正确性需要O(m)。正如我在答案中解释的那样，由于m<n，因此O(n+m)就是O(n)。阅读任何关于大O符号的标准文本，以便理解这一点，如果不明显的话。 - rici