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

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

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

    for i in list1:
        if j in list2:

望大佬指点,感谢!

3个回答

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

下面这个算法需要循环len(list1)*len(list2)次,也就是O(N^2)

Alen_Walker
Alen_Walker 也就是 if...in... 做判断的时候遍历了列表是吧?
大约一年之前 回复

复杂度是O(1)

if key in xxx: 可以理解为这个

def in(key, xxx):
if xxx[key]:
return key
else:
return false

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问