长字符串的 Rabin-Karp 平均用例运行时间
Average case runtime of Rabin-Karp for long strings
我无法理解为什么 Rabin-Karp algorithm 的平均用例运行时间为 O(n+m)，其中 n 是输入字符串的长度，m 是模式字符串的长度.我的理解是，对于所有 n 和 m，运行时间应该是 O(n+m)，即使 n 和 m 非常大。
让我们的散列函数 return 介于 1 和 k 之间的整数。那么在每个位置发生虚假碰撞的概率是 1/k，因此除了一次正确的散列匹配（如果存在匹配）之外，我们期望平均得到 O(n/k) 次虚假碰撞。因此我们期望 O(1+n/k) 哈希匹配。每次我们得到一个匹配项，我们必须检查平均 O(m) 个字符，所以总的平均运行时间是 O((1+n/k)*m).
对于小 n (n<>k)，就是O(n/km)=O(nm)。所以对于大 n，平均运行时间复杂度是 O(nm)，这意味着理论上平均运行时间是 O(nm)，而不是 O(n+m)。但是当然，我们通常处于 n<
如果我们试图绕过碰撞问题，通过随着 n 变大调整 k 以保持碰撞率较低的常数，那么 k 将需要为 O(n)。但是对于大 n，算法仍然是 O(nm)，因为对模式字符串进行散列将花费 O(km)=O(n*m).
我的问题是，这个分析的漏洞在哪里？理论上，Rabin-Karp 实际上是平均情况 O(n*m) 吗？我错过了什么？
首先，您的分析不正确。 hash的size是log(k)，不是k。
其次，通常的假设是事物的大小适合恒定数量的机器字，并且您可以在恒定时间内对它们进行数学运算。
因为你需要k~n，所以hash也是一个机器字，你可以在常数时间内更新hash。
我无法理解为什么 Rabin-Karp algorithm 的平均用例运行时间为 O(n+m)，其中 n 是输入字符串的长度，m 是模式字符串的长度.我的理解是，对于所有 n 和 m，运行时间应该是 O(n+m)，即使 n 和 m 非常大。
让我们的散列函数 return 介于 1 和 k 之间的整数。那么在每个位置发生虚假碰撞的概率是 1/k，因此除了一次正确的散列匹配（如果存在匹配）之外，我们期望平均得到 O(n/k) 次虚假碰撞。因此我们期望 O(1+n/k) 哈希匹配。每次我们得到一个匹配项，我们必须检查平均 O(m) 个字符，所以总的平均运行时间是 O((1+n/k)*m).
对于小 n (n< 如果我们试图绕过碰撞问题，通过随着 n 变大调整 k 以保持碰撞率较低的常数，那么 k 将需要为 O(n)。但是对于大 n，算法仍然是 O(nm)，因为对模式字符串进行散列将花费 O(km)=O(n*m). 我的问题是，这个分析的漏洞在哪里？理论上，Rabin-Karp 实际上是平均情况 O(n*m) 吗？我错过了什么？
首先，您的分析不正确。 hash的size是log(k)，不是k。
其次，通常的假设是事物的大小适合恒定数量的机器字，并且您可以在恒定时间内对它们进行数学运算。
因为你需要k~n，所以hash也是一个机器字，你可以在常数时间内更新hash。