哈希表 复杂度问题
来源：14-7 哈希表更复杂的动态空间处理方法
我爱吃板面
2019-01-06
为什么在改进后的 哈嘻表平均复杂度是 lower_bound ~ upper_bound
比如我们的hashtable 的大小是 4
然后我们的 chaining size upper_bound = 5
那么当 size = 20 的时候 我们就要 resize
好比 size 4 到 8
那么 这个过程resize 方法 需要遍历旧的数组以及这个index的TreeMap 的所有Key(s)
这个大O 是 n^2 (倘若都hash 到了一个 TreeMap并且遍历所有的key)
… 那么…???
所以整个过程平均复杂度怎么就变成了 lower_bound ~ upper_bound?
这个平均下来是怎样转换的呢?
谢谢
写回答
1回答
-
liuyubobobo
2019-01-06
resize不是O(n^2)的，是O(n)的。其中n是所有的元素个数。因为resize的过程遍历了所有的元素。即使你举的特殊情况，所有的元素都在一个hash上，那么遍历这一个hash上的所有元素用O(n)，便利其他hash位置，由于没有元素，所以只是扫了一遍其他hash，也是O(n)，整体还是O(n)的。
之后的计算和我们的动态数组的均摊复杂度分析是一样的。平均再次resize，要再来n个元素。这次resize的n次操作，均摊到后续的每一次操作中，相当于每一操作添加了O(1)的复杂度：）
032019-01-06
相似问题