如何在 python 3.5 中以最少的时间复杂度找到 2 个列表的交集，不包括内置的 set 函数？
How to find intersection of 2 lists in least time complexity in python 3.5 excluding the built in set function?
我知道我们可以用这种方法解决，但我很想知道是否还有其他时间复杂度最低的方法。
a=[1,2,3,4]
b=[2,3,5]
c=set(a).intersection(b)
这给出了答案，但是有更短的方法吗？如果有人在 python 3.5
中解释这个内置函数的时间复杂度，那也会很有帮助
较短的解决方案：
如果你想要一个更短的方法，你可以使用&运算符来sets，这正是一个路口:
>>> a = [1, 2, 3, 4]
>>> b = [2, 3, 5]
>>> c = set(a) & set(b)
{2, 3}
时间复杂度：
Python 有一个名为 timeit 的模块，它测量小代码片段的执行时间。所以在你的情况下：
使用intersection()函数：
$ python3 -m timeit -s "a = [1, 2, 3, 4]; b = [2, 3, 5]; c = set(a).intersection(set(b))"
100000000 loops, best of 3: 0.00989 usec per loop
使用 & 运算符：
$ python3 -m timeit -s "a = [1, 2, 3, 4]; b = [2, 3, 5]; c = set(a) & set(b)"
100000000 loops, best of 3: 0.01 usec per loop
你看他们之间的差别很小（因为在里面他们是一样的东西）。但是没有比set intersection更有效的方法了，因为内置方法已经足够优化了。
Here是Python中每个收集方法的时间复杂度table。看set部分：
- 操作：路口s&t
- 平均情况：O(min(len(s), len(t))
- 最坏情况：O(len(s) * len(t))
- 注意：如果 t 不是集合，请将 "min" 替换为 "max"
我知道我们可以用这种方法解决，但我很想知道是否还有其他时间复杂度最低的方法。
a=[1,2,3,4]
b=[2,3,5]
c=set(a).intersection(b)
这给出了答案，但是有更短的方法吗？如果有人在 python 3.5
中解释这个内置函数的时间复杂度，那也会很有帮助较短的解决方案：
如果你想要一个更短的方法，你可以使用&运算符来sets，这正是一个路口:
>>> a = [1, 2, 3, 4]
>>> b = [2, 3, 5]
>>> c = set(a) & set(b)
{2, 3}
时间复杂度：
Python 有一个名为 timeit 的模块，它测量小代码片段的执行时间。所以在你的情况下：
使用intersection()函数：
$ python3 -m timeit -s "a = [1, 2, 3, 4]; b = [2, 3, 5]; c = set(a).intersection(set(b))"
100000000 loops, best of 3: 0.00989 usec per loop
使用 & 运算符：
$ python3 -m timeit -s "a = [1, 2, 3, 4]; b = [2, 3, 5]; c = set(a) & set(b)"
100000000 loops, best of 3: 0.01 usec per loop
你看他们之间的差别很小（因为在里面他们是一样的东西）。但是没有比set intersection更有效的方法了，因为内置方法已经足够优化了。
Here是Python中每个收集方法的时间复杂度table。看set部分：
- 操作：路口s&t
- 平均情况：O(min(len(s), len(t))
- 最坏情况：O(len(s) * len(t))
- 注意：如果 t 不是集合，请将 "min" 替换为 "max"