在Skiena 的算法设计书中，假设哈希表可以有最大m桶并且元素总数为n，观察到以下更坏情况的时间复杂度：
搜索：O(n)
接班人：O(n + m)
为什么两者不同？寻找后继者在某种程度上不涉及搜索下一个元素吗？
问问题
1206 次
1 回答
6
Hashing achieves constant-time search at the cost of destroying order. When I search for an element, I hash it (O(1)) and look in the chosen bucket (O(n) in the worst case if I scan linearly, as all the other buckets might be empty.)
When I want the next element after a given one, I have no guarantee that it will be in the same bucket. In fact I have no knowledge about where it is at all. Since I do not know what the successor is yet, I can't hash it to find its bucket. Instead I am forced to look in each bucket (O(m).)
If I probe items in order when scanning a bucket, I end up also doing a total of linear work in the number of items (O(n)). This results in a total complexity of O(n + m).
于 2012-05-12T23:58:31.867 回答