list 和 dict 的常用操作时间复杂度分别是多少？

list 底层是动态数组，dict 底层是哈希表，复杂度由此决定。

list（n 为长度）：

• 索引取值/赋值 a[i]：O(1)
• 尾部 append、pop()：均摊 O(1)（扩容时 O(n)，均摊后常数）
• 头部或中间 insert(0, x)、pop(0)、del a[i]：O(n)，需搬移元素
• x in a 成员判断、按值 remove：O(n) 线性扫描
• 切片 a[i:j]：O(k)，k 为切片长度；排序 Timsort 为 O(n log n)

dict：

• 取值、赋值、删除、in 判断：平均 O(1)，最坏（大量哈希冲突）退化为 O(n)，但现实中极少发生
• 遍历：O(n)

易错点与建议：需要频繁头部出队时用 collections.deque（两端 O(1)）；把 list 当集合做 in 判断是常见性能坑，数据量大应换 set/dict。追问方向：动态数组的扩容策略（CPython 约按 1.125~2 倍渐进扩容，保证均摊 O(1)）、dict 的开放寻址与装载因子、为什么字典查找受哈希冲突影响。