Python中list和set的时间复杂度问题，求解答
AList = [1,2,3]
BSet = {1,2,3}
问：
- 从 AList 和 BSet 中查找 4，最坏时间复杂度哪个大？
- 从 AList 和 BSet 中插入 4，最坏时间复杂度哪个大？
Python中list和set的时间复杂度问题，求解答
12 回复
在Python里，list和set的核心区别在于底层数据结构，这直接决定了它们操作的时间复杂度。
List（列表） 底层是动态数组。
- 查找 (
x in list)： 平均和最坏情况都是 O(n)，需要遍历整个列表。 - 插入 (
append)： 在末尾是 O(1) 平摊时间；在中间或开头 (insert) 是 O(n)，因为需要移动后续元素。 - 删除 (
remove,pop指定位置)： 平均和最坏情况是 O(n)，因为同样涉及元素移动。
Set（集合） 底层是哈希表。
- 查找 (
x in set)： 平均是 O(1)，最坏情况（全冲突）是 O(n)，但通常性能极佳。 - 插入 (
add)： 平均 O(1)，最坏 O(n)。 - 删除 (
remove)： 平均 O(1)，最坏 O(n)。
简单总结：需要频繁查找、去重或检查成员是否存在时，用set；需要保持顺序、通过索引访问或允许重复元素时，用list。
楼主描述不太清楚啊。一般是顺序结构跟链式比较复杂度。很少线性表跟哈希表比较复杂度啊。正常来说值比较线性表复杂度是 On，哈希是 O1。看你提供的是有序顺序结构，看数据量决定要不要建索引。复杂度都是可以优化的，比如顺序结构折半查找可以实现 lgn
看看源码就知道了
list 是数组, append 是 O(1), 而 insert 因为要把元素往后移, 所以最坏是 O(n), 比如 insert(0, x)
set 是哈希表, 基本上加入只是求 hash 位置, 基本上是 O(1), 更细节一点的话, set 的 hash 寻址是二次散列和顺序寻址结合的, 不过基本上也可以看成算是 O(1)
