[問題] 關於Python的Set

[bin90909 (Ben)]

    大家好, 想請問一個問題(困擾我很久了), 就是如果我建一個Set, 裡面

都放整數, 那用in搜尋一個特定點的時候他的time complexity是多少?(只需

知道存不存在此點.)

    另外想請問大家有沒有推薦的二維整數點搜尋方法? 謝謝大家的回答!!

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.113.5.201
→ kenzou:average case O(1)/ worst case O(n)
→ uranusjr:其實這要看實作...不過如果是用 Linked List 實作的 Hash
→ uranusjr:Table（同 Java 的實作法）那最壞是 O(n), 然後 O(1) 應
→ uranusjr:該是最好狀況吧...
→ yjc1:這種情況可以考慮用 bloom filter
→ bin90909:謝謝大家的建議!! 另外這個資料結構也需要支援快速刪點
→ bin90909:不知道有沒有更合適的方法?(目前有實做2-D linked list)
→ bin90909:和(Dictionary+set)這兩種data structure
→ uranusjr:看起來用 dict 很適合, 把每個物件加個 ID 當 key 來找