[問題] 請問insertion, find均為O(1)的資料結構
看板Prob_Solve (計算數學 Problem Solving)作者king19880326 (OK的啦～我都可以接受)時間16年前 (2008/11/29 19:47)推噓0(0推 0噓 5→)留言5則, 4人參與討論串1/1
是這樣的
小弟最近寫的一個程式
需要一種能動態增減的資料結構.
需要提供的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
→
11/30 17:52, , 1F
11/30 17:52, 1F
→
12/01 04:45, , 2F
12/01 04:45, 2F
→
12/01 19:53, , 3F
12/01 19:53, 3F
→
12/01 19:54, , 4F
12/01 19:54, 4F
→
12/02 05:00, , 5F
12/02 05:00, 5F
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
