参考：https://blog.csdn.net/baoli1008/article/details/48059623
注：下文中，’n’代表容器中元素的数量，’k’代表参数的值，或者参数的数量。
1.列表（list）
-
以完全随机的列表考虑平均情况。
-
列表是以数组（Array）实现的。
-
最大的开销发生在超过当前分配大小的增长，这种情况下所有元素都需要移动；或者是在起始位置附近插入或者删除元素，这种情况下所有在该位置后面的元素都需要移动。
-
如果需要在一个队列的两端进行增删的操作，应当使用collections.deque（双向队列）
-
操作 操作说明 时间复杂度（平均情况） 时间复杂度（最坏情况） index(value) 查找list某个元素的索引 O(1) O(1) a=index(value) 索引赋值 O(1) O(1) list[:] 列表复制 O(n) O(n) list.append(value) 队尾添加 O(1) O(1) list.insert(index, value) 根据索引插入某个元素 O(n) O(n) list[index] 取元素 O(1) O(1) list[index]=value 赋值 O(1) O(1) list.pop() 队尾删除 O(1) O(1) list.pop(index) 根据索引删除某个元素 O(n) O(n) [i for i in list] 遍历/迭代 O(n) O(n) list[m:n] 取切片 O(k) O(k) del list[m:n] 删除切片 O(n) O(n) list[m:n]=[n] 更改切片 O(k+n) O(k+n) list.extend([]) 列表扩展 O(k) O(k) list.sort() 列表排序 O(nlogn) O(nlogn) list*n 列表乘法 O(nk) O(nk) i in list 列表搜索 O(n) min(list), max(list) 取最大和最小值 O(n) len(list) 计算长度 O(1) O(1)
2.字典（dict）
- 下列字典的平均情况基于以下假设：
- 对象的散列函数足够健壮（robust），不会发生冲突。
- 字典的键是从所有可能的键的集合中随机选择的。
-
操作 操作说明 平均情况 最坏情况 copy 复制 O(n) O(n) dict[key] 取元素 O(1) O(n) dict[key]=value 更新元素 O(1) O(n) del dict[key] 删除元素 O(1) O(n) [i for i in dict] 遍历字典 O(n) O(n) i in dict 搜索元素 O(1) O(1)
3.集合（set）
-
操作 操作说明 平均情况 最坏情况 i in set 搜索元素 O(1) O(n) set_1 | set_2 并集 O(len(set_1)+len(set_2)) set_1 & set_2 交集 O(min(len(set_1), len(set_2)) O(len(set_1) * len(set_2)) set_1 - set_2 差集 O(len(set_1)) set.difference_update(set_2) 更新 O(len(set_2)) set^t 对称差集 O(len(set)) O(len(set) * len(t)) set.symmetric_difference_update(t) O(len(t)) O(len(t) * len(set))
- 差集（set_1 - set_2，或set_1.difference(set_2)）运算与更新为差集（set_1.difference_uptate(set_2)）运算的时间复杂度并不相同：
- 前者是将在set_1中，但不在set_2中的元素添加到新的集合中，因此时间复杂度为O(len(set_1))。
- 后者是将在set_2中的元素从set_1中移除，因此时间复杂度为O(len(set_2))。