python 里面内置的 in 时间复杂度

今天看之前实现的剑指 offer 的第一题 二维数组中的查找 博文时 https://blog.csdn.net/qq_43657442/article/details/105969936，有这么一个实现

# -*- coding:utf-8 -*- class Solution: # array 二维列表 def Find(self, target, array): for line in array: #遍历每一行 if target in line: #目标在这行里面吗 return True return False # write code here

        然后我就想这个的时间复杂度怎么样呢，我感觉就像双循环暴力查找，应该 o(n²)，但是没确定把握 in 的时间复杂度是 o(n)，就找了一下资料

结论

        列表的 in 是 o(n)        字典、集合、双向队列的 in 是 o(1)，这个双向队列我用的比较少，不太熟悉

        有点简单猜测这个复杂度和实现列表、字典、集合的数据结构，存储方式有关。

       

list 就是个指针数组，指针数组里面对应存放了每个元素所在的地址

               

        列表的存储方式是顺序存储的，最终总结 python中 list 到底是怎么实现的，内存里面是怎么存放的这篇文章讲的应该蛮清楚了，里面也有 list 实现的底层代码链接，有兴趣的可以自己看看。但是集合、字典是怎么实现的，我需要去看看底层代码

        双向队列估计是是双向链表实现的，链式存储的

        等我找找 set 、dict的底层实现代码再来更新