→ TonyQ:做個不會有collision 的hashtable ? :p 11/30 17:52
→ king19880326:collision與否可能沒辦法在寫程式的時候確定喔 @@>? 12/01 04:45
→ progden:這需要堅強的理論分析 -o_o- 12/01 19:53
→ progden:是做甚麼用途呢? 加上些限制 或許比較容易討論 12/01 19:54
→ ferng1021:perfect hashing? 12/02 05:00
是這樣的
小弟最近寫的一個程式
需要一種能動態增減的資料結構.
需要提供的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