作者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