为何Python中集合求数组交集的运行速度慢于数组方法？

首先纠正你对时间复杂度的错误认知：

• 你标注数组方法是O(m*n)，但实际并非如此——因为你用的是Python的range对象，不是普通列表。i in range(a, b)不会遍历整个序列，而是通过数学计算直接判断a ≤ i < b，时间复杂度是O(1)。所以第一个方法的实际复杂度是O(m)（m是A的长度），只需要遍历A的每个元素，做一次O(1)的判断。
• 集合方法也不是O(1)，转集合的过程需要遍历整个range对象，把每个元素加入集合，这一步的复杂度是O(m+n)（m是A的长度，n是B的长度），之后求交集的复杂度是O(min(m,n))，总复杂度是O(m+n)。

这次测试里集合方法更慢的核心原因：
你的A是range(50,1000000)（近百万个元素），B是range(-1000000,60)（超百万个元素），把这两个大序列转成集合的开销非常大，远远超过了第一个方法里遍历A+做O(1)判断的总耗时。

如果把range换成真正的列表，比如：

A = list(range(50,1000000))
B = list(range(-1000000,60))

再跑测试，你会发现第一个方法直接慢到离谱（此时i in B变成遍历整个列表，O(n)，总复杂度O(m*n)），而集合方法会快很多——这才符合你原本的理论认知。

另外，集合方法里用set_a.intersection(set_b)会比列表推导式更高效，因为这是Python底层用C实现的操作，但转集合的开销还是无法避免。

内容的提问来源于stack exchange，提问作者Katsu