遇到一个 list 和 set 时间复杂度的问题，哪个老哥帮忙解答下

[smallQ]

AList = [1,2,3]
BSet = {1,2,3}

问：

1. 从 AList 和 BSet 中查找 4，最坏时间复杂度哪个大？
   
2. 从 AList 和 BSet 中插入 4，最坏时间复杂度哪个大？

[swulling]

A
A

[clino]

set 没有插入概念吧，应该说加入

[lniwn]

看图 https://i.loli.net/2018/06/01/5b112d2fbfb22.png

[enenaaa]

弄清楚列表和哈希表的区别就好了。
1. 对于查找， 列表时间复杂度是 O(n)，set 是 O(1)。 所以列表的时间复杂度更大。
2. 对于插入， 两个都是 O(1)

[fuchaofather]

楼主描述不太清楚啊。一般是顺序结构跟链式比较复杂度。很少线性表跟哈希表比较复杂度啊。正常来说值比较线性表复杂度是 On，哈希是 O1。看你提供的是有序顺序结构，看数据量决定要不要建索引。复杂度都是可以优化的，比如顺序结构折半查找可以实现 lgn

[fuchaofather]

还有线性表插入顺序结构首尾插入效率又不一样，哈希表示哈希后 put

[suber]

最坏时间复杂度，应该要考虑哈希出现碰撞，而 Python 的实现是开放寻址。不确定 set 最坏复杂度是不是 O(n)

[smallQ]

这是今天群里面看到的一道面试题，，

[tkmiles]

看看源码就知道了

list 是数组, append 是 O(1), 而 insert 因为要把元素往后移, 所以最坏是 O(n), 比如 insert(0, x)

set 是哈希表, 基本上加入只是求 hash 位置, 基本上是 O(1), 更细节一点的话, set 的 hash 寻址是二次散列和顺序寻址结合的, 不过基本上也可以看成算是 O(1)

[smallQ]

@tkmiles tks

[Jayce245]

set 是 o(1 ）啊，当然比 list O(n)快