algorithm - 运行时分析中的概率？

Question

这是一道家庭作业题，我对它的正确方法感到非常困惑。

存在一个包含m 个槽位 的哈希表。我们假设Simple Uniform Hashing assumption (SUHA)。

我们执行 n 个插入操作，但所有 n 个元素都映射到插槽 0。(这不太可能，但有可能)。

现在问题要求搜索一个随机键“x”，其散列值可能存在也可能不存在于表中。 完成搜索的运行时上限是多少？

这是我的方法:

由于我们假设 SUHA，因此 key 散列到槽的概率为 1/m。如果 key 确实散列到槽 0，则搜索需要 O(n) 时间，否则需要 O(m-1) 时间。按照这种逻辑，解决方案是否为 [1/m]*O(n)+[(m-1)/m]*O(m-1) 简化为 O(n/m + [(m-1) ^2]/米)。

<强>1。概率可以以这种方式乘以渐近运行时间吗？

<强>2。甚至可能在确定运行时方面发挥作用？

Answer 1

我相信你想错了。不应考虑概率。由于问题是询问上限，请将该问题转化为，最坏的情况是什么？

最坏的情况是 x 像之前的每个哈希值一样哈希为 0。现在假设 x 是散列的最后一个元素。根据碰撞解决方案，您必须遍历可能的位置，直到找到您要查找的元素。这将使它成为 O(n)，因为它取决于问题中所示的 n 个先前哈希的数量。

最好的情况就是，如果 x 没有散列为 0。由于计算散列是 O(1)，一旦你散列到一个键，它要么存在，要么不存在，另一个 O(1) 操作使得总的来说，O(1) 操作。