Python内置结构时间复杂度

列表（list）

以完全随机的列表考虑平均情况。

列表是以数组（Array）实现的。最大的开销发生在超过当前分配大小的增长，这种情况下所有元素都需要移动；或者是在起始位置附近插入或者删除元素，这种情况下所有在该位置后面的元素都需要移动。如果你需要在一个队列的两端进行增删的操作，应当使用collections.deque（双向队列）

图1-1 列表复杂度

双向队列（collections.deque）

deque （double-ended queue，双向队列）是以双向链表的形式实现的 (Well, a list of arrays rather than objects, for greater efficiency)。双向队列的两端都是可达的，但从查找队列中间的元素较为缓慢，增删元素就更慢了。

图1-2 双向队列复杂度

集合（set）

未列出的操作可参考 dict —— 二者的实现非常相似。

操作平均情况最坏情况

图1-3 集合复杂度

字典（dict）

下列字典的平均情况基于以下假设：

1. 对象的散列函数足够撸棒（robust），不会发生冲突。

2. 字典的键是从所有可能的键的集合中随机选择的。

小窍门：只使用字符串作为字典的键。这么做虽然不会影响算法的时间复杂度，但会对常数项产生显著的影响，这决定了你的一段程序能多快跑完。

图1-4 集合复杂度