PTT數位生活區 / Python

[問題] 關於Python的Set

看板Python作者 (Ben)時間14年前 (2011/03/11 11:58), 編輯推噓0(0推 0噓 9→)
留言9則, 4人參與, 最新討論串1/1
大家好, 想請問一個問題(困擾我很久了), 就是如果我建一個Set, 裡面 都放整數, 那用in搜尋一個特定點的時候他的time complexity是多少?(只需 知道存不存在此點.) 另外想請問大家有沒有推薦的二維整數點搜尋方法? 謝謝大家的回答!! -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.113.5.201
→
03/11 13:03, , 1F
average case O(1)/ worst case O(n)
03/11 13:03, 1F
→
03/11 14:02, , 2F
其實這要看實作...不過如果是用 Linked List 實作的 Hash
03/11 14:02, 2F
→
03/11 14:03, , 3F
Table（同 Java 的實作法）那最壞是 O(n), 然後 O(1) 應
03/11 14:03, 3F
→
03/11 14:03, , 4F
該是最好狀況吧...
03/11 14:03, 4F
→
03/11 23:21, , 5F
這種情況可以考慮用 bloom filter
03/11 23:21, 5F
→
03/11 23:46, , 6F
謝謝大家的建議!! 另外這個資料結構也需要支援快速刪點
03/11 23:46, 6F
→
03/11 23:47, , 7F
不知道有沒有更合適的方法?(目前有實做2-D linked list)
03/11 23:47, 7F
→
03/11 23:47, , 8F
和(Dictionary+set)這兩種data structure
03/11 23:47, 8F
→
03/12 03:31, , 9F
看起來用 dict 很適合, 把每個物件加個 ID 當 key 來找
03/12 03:31, 9F
‣ 更多 bin90909 的文章
文章代碼(AID): #1DUPu17F (Python)
Python 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 bin90909 的文章
文章代碼(AID): #1DUPu17F (Python)