公开寻址的平均时间复杂性
来自 CLRS 书籍分析：
11.6：给定一个负载因子 α=n/m<1 的开放地址哈希表，假设均匀哈希，不成功搜索中的预期探测数量最多为 1/1-α。
11.7：假设均匀散列，将一个元素插入到负载因子为 α 的开放地址哈希表中平均最多需要 1/1-α 探测。
11.8: 给定一个负载因子 α<1 的开放地址哈希表，假设均匀散列并假设 中的每个键，成功搜索中的预期探测数量最多为 (1/α)ln(1/1-α)该表同样可能被搜索。
读完这一章后，我不明白插入和搜索的平均时间复杂度是 O(1/1-α) 还是 O(1) 还是其他。
寻找解释。
From CLRS book analysis:
11.6: Given an open-address hash table with load factor α=n/m<1 the expected number of probes in an unsuccessful search is at most 1/1-α assuming uniform hashing.
11.7: Inserting an element into an open-address hash table with load factor α requires at most 1/1-α probes on average, assuming uniform hashing.
11.8: Given an open-address hash table with load factor α<1, the expected number of probes in a successful search is at most (1/α)ln(1/1-α) assuming uniform hashing and assuming that each key in the table is equally likely to be searched for.
After reading the chapter I don't understand if the averege time complexity of insert and search is O(1/1-α) or O(1) or something else.
Looking for an explanation.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
现在让我们关注 O(1 / (1 - α)) 位。如果 α 具有任意固定值（例如 α = 0.75），则 1 / (1 - α) 将是一个常数，整个表达式的复杂度将为 O(1)。因此，从这个意义上说，所有上述纯粹依赖于 α 的运行时间都可以解释为“对于任何固定的 α 值，这些都是 O(1)”。
那么为什么不在 CLRS 中直接说“O(1)”呢？原因是，对 α 进行更精确的分析可以指导哈希表的运行时间如何随着 α 的变化而变化。例如，假设您要将 α 从 0.90 提高到 0.99。知道运行时间为 O(1 / (1 - α)) 后，您就会知道性能会下降 10 倍。然而，将 α 从 0.50 移至 0.59 对性能的影响明显较小。
Let’s focus on the O(1 / (1 - α)) bit for now. If you have any fixed value of α (say, α = 0.75), then 1 / (1 - α) will be a constant, and the entire expression will be O(1). So in that sense, all of the above runtimes that depend purely on α can be interpreted as “these are all O(1) for any fixed value of α.”
So why not just say “O(1)” in CLRS? The reason is that the more precise analyses in terms of α provide guidance about how the runtimes of the hash table will change as α changes. For example, suppose you want to raise α from 0.90 to 0.99. Knowing that the runtime is O(1 / (1 - α)) then tells you than you should expect to see a 10x slowdown in performance. However, moving α from 0.50 to 0.59 will have a markedly smaller impact on performance.