algorithm - 有人可以向我解释 Rabin-Karp 算法的复杂性吗？

Question

我试图理解为什么 Rabin-Karp 算法的最坏情况运行时间是 O(nm) 而平均情况是 O(n+m)。

有人可以帮我吗？

Answer 1

Rabin-Karp 是最坏情况O(nm)，因为它可能在每个点（其中有 ）都发现误报，n并且它可能需要最多m比较来验证匹配，因为您需要实际比较字符串。

使用一个不应该发生的甚至一半合理的散列函数，但是对于任何散列函数来说，都可以制作一个表现出上述病态行为的查询（即，正在搜索的字符串和子字符串）。

因此，尽管 RK 预计时间复杂度为 O(n)，但最坏情况的时间复杂度为 O(nm)。（注意：因为m必须不大于n，n + m所以有界2n，因此 O(n + m) 与 O(n) 相同。）

如果问题是找到所有匹配的子字符串，则更容易产生 O(nm) 行为，这是经常使用 RK 的另一个上下文。在这种情况下，在由m as 组成的字符串中搜索由 s 组成的子字符串n a肯定会花费nm时间，因为子字符串需要在源字符串中的每个点都匹配。

存在其他算法来查找在 n 中仍然是线性的所有子串，即使在病态情况下也是如此。

Answer 2

Wiki很好地解释了算法的时间复杂度。

可以说，哈希计算函数的有效性（理解为在恒定时间内动态重用已经计算的哈希值的能力）是算法计算时间复杂度的决定因素。

让我们看看哈希计算是如何产生这种差异的。

---

时间复杂度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

给予，O(m) + O(n)*O(1)= O(m) + O(n)=O(m+n)