17370845950

列表随机访问O(1)但首部插入删除O(n)，元组不可变且更轻量；字典和集合平均O(1)依赖哈希表，查存在性优先用set；deque两端操作O(1)，适合队列场景。

列表 vs 元组：随机访问快，但插入删除慢

Python 的 list 是动态数组，底层连续分配内存，所以

list[i] 是 O(1) 时间；但 list.insert(0, x) 或 list.pop(0) 是 O(n)，因为要移动后续所有元素。
tuple 不可变，创建后内存固定，访问同样 O(1)，但无法增删——这不是限制，而是提示你：如果数据只读、且长度已知，用 tuple 更轻量，还能作为字典键。

• 频繁在头部/中部插入？别硬扛 list，改用 collections.deque
• 循环中反复调用 list.append() 是安全的，Python 已做倍增扩容优化
• 把大 list 传给函数时，注意是引用传递；若不希望被意外修改，传 my_list.copy() 或 list(my_list)

字典和集合的平均 O(1) 不是白来的

dict 和 set 底层靠哈希表实现，理想情况下查找、插入、删除都是平均 O(1)。但实际性能受哈希冲突和负载因子影响：

• 键类型必须可哈希（list、dict 不行，tuple 可以）
• 如果自定义类作键，必须正确定义 hash 和 eq
• 大量插入后，Python 会自动扩容重哈希，这时单次操作可能卡到 O(n)——但均摊仍是 O(1)
• 用 in 判断存在性：对 list 是 O(n)，对 set 是 O(1)，差距在十万级数据上就明显

当你要频繁查“有没有”，别用 list in

写 if x in my_list: 看似自然，但每次都是线性扫描。换成 my_set = set(my_list) 后再查，初始化多花 O(n)，但后续每次 in 都省下大量时间。

• 初始化成本可接受？比如数据只建一次、查几百次 → 换 set
• 数据实时变动？用 set 同步增删，比每次重建划算
• 内存敏感？set 比 list 占更多内存（哈希表有空槽），但通常值得
• 注意：set 不保序，如果顺序重要，Python 3.7+ 的 dict 可模拟有序集合：{x: None for x in items}

deque 在队列场景下比 list 稳定得多

list 做队列（append() + pop(0)）看似简单，但 pop(0) 每次都 O(n)。而 collections.deque 是双向链表+块状缓冲，两端操作都是 O(1)。

• BFS、滑动窗口、任务队列等场景，直接上 deque
• deque 支持 appendleft()、popleft()、extendleft()，语义清晰
• 不要用 deque[i] 随机访问——虽然支持，但退化为 O(n)，不如转成 list 再取
• 创建空 deque 开销略大于 list，但微乎其微；真正影响性能的是操作模式，不是构造本身

实际选型时，别只看「哪个更快」，要看「哪次操作最常发生」。一个算法里查 10 万次存在性，哪怕初始化多花 5ms，也远小于累计 2 秒的线性扫描。而很多人卡在“习惯写 list”，没意识到自己正在用 O(n) 解决本该 O(1) 的问题。