Python维基上没有提及多集合交集
的平均复杂度:
https://wiki.python.org/moin/TimeComplexity
只给出了最坏情况的复杂度:
(n-1)*O(l) where l is max(len(s1),..,len(sn))
多集合交集
操作的平均复杂度是多少?这个操作在底层是如何实现的?
set.intersection(s1,s2,s2,s4 ...sn)
在Python-wiki中,因为它们的最坏情况复杂度不同,多集合交集
操作是否以与两个集合交集
操作不同的方式实现:
2个集合的交集: O(len(s) * len(t))
多个集合的交集: (n-1)*O(l),其中l是max(len(s1),..,len(sn))
因此,使用多集合公式的两个集合的复杂度应该是:
--> (2-1)*O(l) where l is max(len(s1), len(s2)`
--> O(max(len(s1), len(s2))
我认为它与两个集合交集操作的复杂度符号表示相当不同。
顺便说一下,除了使用集合交集进行不同集合之间的成员检查外,是否有更好的方法?
注意:我希望得到的是解释而不仅仅是复杂度O()符号表示 :)
intersect_multi
没有包括平均值。我最后一句话的意思是,对我来说,普通intersect
的最坏情况复杂度似乎没有包括在intersect_multi
的最坏情况中。 - Graipher