pho*_*nix 38 java time-complexity
在最坏的情况下contains,单个查找操作OR 是否O(n)合适？那么,对于n元素的查找hashSet会是O(n^2)什么？
contains
O(n)
n
hashSet
O(n^2)
JB *_*zet 61
是的,但这确实是最糟糕的情况:如果所有元素HashSet都具有相同的哈希码(或者哈希码导致相同的桶).使用正确写入hashCode和正态分布的密钥样本,查找为O(1).
HashSet
hashCode
kra*_*pse 6
是的,但是我们拥有HashSets的全部原因是我们遇到这种最坏情况的概率非常非常低,并且它通常比堆的保证nlogn或(自平衡)TreeSet要快得多,或者保证n ^ 2对于未分类的列表.
归档时间：
14 年，11 月 前
查看次数：
34058 次
最近记录：
8 年，7 月 前