本文旨在分析python四大数据结构list、tuple、dict、set的原理和操作时间复杂度，以便在实际场景中按照需求做出正确的选择。
List
列表(list)是python中最常用的数据结构之一，基于数组实现，区别于静态数组的是其动态增长的特性使其非常灵活，比如
1 | a = [1, 2] |
当其初始化的内存大小不能满足append新元素的需求时，会为它进行扩容。
其最大的时间开销为最坏情况下的delete和insert操作，以及超过当前长度重新分配内存区域时。
| Operation | 平均情况时间复杂度 | 最坏情况时间复杂度 |
|---|---|---|
| append | O(1) | O(1) |
| insert | O(n) | O(n) |
| index | O(1) | O(1) |
| delete | O(n) | O(n) |
| for i in list | O(n) | O(n) |
| len(list) | O(1) | O(1) |
| sort | O(nlogn) | O($n^2$) |
| pop | O(1) | O(1) |
Tuple
tuple元组是不可变的list类型，不能进行增删改操作
1 | a = (1, 2, 3, 4) |
注意此时c引用的是新的对象
| Operation | 平均情况时间复杂度 | 最坏情况时间复杂度 |
|---|---|---|
| index | O(1) | O(1) |
| count(tuple) | O(n) | O(n) |
| len(tuple) | O(1) | O(1) |
| for i in tuple | O(n) | O(n) |
Dict
dict采用了hash表实现，key通过hash函数映射为一个int，对元素个数取模后得到对应的数组index，通过index即可访问到value，注意key是不可更改的，但value可更改。
dict解决hash冲突的方式：开放定址法，在发生冲突时，假设当前位置为A，那么继续探测A+1处是否冲突，直到不冲突为止，将value放进该处。
| Operation | 平均情况时间复杂度 | 最坏情况时间复杂度 |
|---|---|---|
| index | O(1) | O(n) |
| delete | O(1) | O(n) |
| for k,v in d.items() | O(n) | O(n) |
| len(dict) | O(1) | O(1) |
Set
set集合的实现也为hash表，与dict相似，key仍然是通过hash函数映射为一个int，对元素个数取模后得到对应的数组index，但value为空。set实现了大部分的集合运算，如求交集、并集等，但不支持通过下标访问。
| Operation | 平均情况时间复杂度 | 最坏情况时间复杂度 |
|---|---|---|
| for i in set | O(n) | O(n) |
| s | t | O(len(s)+len(t)) | O(len(s)+len(t)) |
| s & t | O(min(len(s), len(t)) | O(len(s)*len(t)) |
| s - t | O(len(s)) | O(len(s)) |
总结
本文对python四大数据结构做了初步的分析，其中部分api的性能有待补充。
