Alen_Walker
2019-06-09 20:12
采纳率: 100%
浏览 1.5k

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

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

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

    for i in list1:
        if j in list2:

望大佬指点,感谢!

  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

3条回答 默认 最新

  • 观点小号 2019-06-12 16:12
    已采纳

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

    打赏 评论
  • threenewbee 2019-06-09 21:32

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

    打赏 评论
  • 小熊之怒 2019-06-12 20:09

    复杂度是O(1)

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

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

    打赏 评论

相关推荐 更多相似问题