list & dict——Python数据结构

list与dic的操作

list常用操作性能

list常用操作的算法复杂度

1. 取值、赋值

取值 v = a[i] ，赋值 a[i] = v 均为 O(1) 复杂度

2. 列表增长

liist.append(v) 为 O(1)
liist = liist + liist2 为 O(n+k), k 为 liist2 的长度

3. 列表生成

• 列表连接（循环 + ） 最慢

l = []
for i in range(100):
  l = l + [i]

• append

l = []
for i in range(100):
  l.append(i)

• 列表推导式

l = [i for i in range(100)]

• range 函数转换 最快

l = [i for i in range(100)]

---

dict常用操作性能

dict 取值操作通过 key 查找实现，不同于 list 通过 index 查找

dict常用操作算法复杂度