algorithm - 有人可以向我解释 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) 相比，additive 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)