作者king19880326 (OK的啦～我都可以接受)
看板Prob_Solve
标题[问题] 请问insertion, find均为O(1)的资料结构
时间Sat Nov 29 19:47:47 2008
是这样的
小弟最近写的一个程式
需要一种能动态增减的资料结构.
需要提供的operation有
insert(insert一个新的data进去该data structure)
find(判断data是否在该data structure里, 若是, 则提供data所在的position)
因为该程式几乎不会用到deletion(自data structure里delete data)
所以不在意deletion的效能
目前我是使用linked list来实作这个部分
可是linsked list的find的time complexity为O(n)
(即使是amortized下依然是O(n))
想请问有没有一个资料结构的insert和find的time complexity是O(1)
(或是amortized後为(1)的??)
感谢感谢 <(_ _)>
ps. hash table虽然可以办到, 可是在collision的时候就不能保证O(1)了 @@>
感谢大家 <(_ _)>
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.243.192
※ 编辑: king19880326 来自: 140.112.243.192 (11/29 19:55)
※ king19880326:转录至看板 C_and_CPP 11/29 23:51
※ king19880326:转录至看板 Programming 11/29 23:51
1F：→ TonyQ:做个不会有collision 的hashtable ? :p 11/30 17:52
2F：→ king19880326:collision与否可能没办法在写程式的时候确定喔 @@>? 12/01 04:45
3F：→ progden:这需要坚强的理论分析 -o_o- 12/01 19:53
4F：→ progden:是做甚麽用途呢? 加上些限制 或许比较容易讨论 12/01 19:54
5F：→ ferng1021:perfect hashing? 12/02 05:00