我正在研究哈希表,然后想到了:
为什么不使用字典搜索元素,而不是先对列表排序然后进行二进制搜索?(假设我要搜索多次)
O(n)
(我认为)时间内将列表转换为字典,因为我们必须遍历所有元素。O(1)
时间O(1)
时间(平均)中搜索任何元素,这O(n)
是最坏的情况现在,如果我们谈论平均大小写O(n)
优于其他排序算法,因为最多只能采用它们O(nlogn)
。如果我对我所说的所有内容都是正确的,那为什么不这样做呢?
我知道您可以对未排序的字典或数组中的已排序元素执行其他各种操作,但是如果我们只坚持搜索,那么这不是比其他排序算法更好的搜索方法吗?
是的,精心设计的哈希表可以胜过排序和搜索。
对于一个适当的选择,有很多因素会起作用,例如就地需求,数据集的动态性,搜索数量与插入/删除的数量,易于构建有效的哈希函数...
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句