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

Question

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

有人可以帮我吗？

Answer 1

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)

Answer 2

拉宾，卡普是最坏情况O（纳米），因为它可能会发现在每一个点（其中有假阳性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 中仍然是线性的子串，即使在病理情况下也是如此。