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