我想知道python的set.intersection的复杂度。我查看了 python 的文档和在线维基，但我没有发现这种方法对多组的时间复杂度。
最佳答案
python wiki on time complexity lists单个交集为 O(min(len(s), len(t)) 其中 s 和 < em>t 是集合的大小，t 是一个集合。(英语:时间受较小集合的大小限制，并且与较小集合的大小成线性关系。)
注意:根据下面的评论，如果传递的参数不是集合，则此 wiki 条目是错误的。我已更正维基条目。
如果你有 n 个集合(集合，不是可迭代对象)，你将做 n-1 个交集，时间可以是 (n-1)O(len(s)) 其中s是尺寸最小的集合。
请注意，当您进行交集时，结果可能会变小，因此尽管 O 是最坏的情况，但实际上，时间会比这更好。
然而，looking at the specific code这种采用 min() 的想法仅适用于一对集合，不会扩展到多个集合。所以在这种情况下，我们不得不悲观，将s作为尺寸最大的集合。
关于python - n个集合的python "set.intersection"的时间复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30845469/