python中关键字in对列表时的判断逻辑是怎样的？

Question

我想知道python中使用if key in list 的时候，是怎么判断key有没有在列表中的，比如有没有遍历list？

问这个问题的原因是因为我纠结于下面这代码的时间复杂度是多少：

    for i in list1:
        if j in list2:

望大佬指点，感谢!

Answer 1

O（n^2）if ...in... 做遍历了
如果觉得复杂度高的话可以考虑改用字典，或集合。
python中list对象的存储结构采用的是线性表，因此其查询复杂度为O(n),而dict对象的存储结构采用的是散列表(hash表)，其在最优情况下查询复杂度为O(1)。