Python常用数据类型时间和空间复杂度
O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n²logn)<O(n³)<O(2ⁿ)<O(n!)<O(nⁿ)
列表(list)
- python的列表内部实现是数组(具体实现要看解析器)
- 拥有数组的特点,超过容量会增加更多的容量,set, get 是O(1),但del,insert,,in的性能是O(n)
- 'n'是容器中当前的元素数'k'是需要操作的元素个数
| 操作 |
平均情况 |
最坏情况 |
| 复制 |
O(n) |
O(n) |
| append[注1] |
O(1) |
O(1) |
| 插入 |
O(n) |
O(n) |
| 取元素pop |
O(1) |
O(1) |
| 取元素pop[1] |
O(n) |
O(n) |
| 更改元素 |
O(1) |
O(1) |
| 删除元素 |
O(n) |
O(n) |
| 遍历 |
O(n) |
O(n) |
| 取切片 |
O(k) |
O(k) |
| 删除切片 |
O(n) |
O(n) |
| 更改切片 |
O(k+n) |
O(k+n) |
| extend[注1] |
O(k) |
O(k) |
| 排序 |
O(n log n) |
O(n log n) |
| 列表乘法 |
O(nk) |
O(nk) |
| x in s |
O(n) |
|
| min(s), max(s) |
O(n) |
|
| 计算长度 |
O(1) |
O(1) |
双向队列（collections.deque）：
- double-ended queue,双向队列,是以双向链表的形式实现的
- 双向队列的两端都是可达的但查找队列中间的元素较为缓慢,增删元素就更慢了
| 操作 |
平均情况 |
最坏情况 |
| 复制 |
O(n) |
O(n) |
| append |
O(1) |
O(1) |
| appendleft |
O(1) |
O(1) |
| pop |
O(1) |
O(1) |
| popleft |
O(1) |
O(1) |
| extend |
O(k) |
O(k) |
| extendleft |
O(k) |
O(k) |
| rotate |
O(k) |
O(k) |
| remove |
O(n) |
O(n) |
字典(dict):
- 关于字典需要了解的是hash函数和哈希桶
- 一个好的hash函数使用到的哈希桶中的值只有一个,若多个key hash到了同一个哈希桶中,称之为哈希冲突
- 查找值时,会先定位到哈希桶中,再遍历hash桶,在hash基本没有冲突的情况下get,set,delete, in方面都是O(1)。
| 操作 |
平均情况 |
最坏情况 |
| 复制[注2] |
O(n) |
O(n) |
| 取元素 |
O(1) |
O(n) |
| 更改元素[注1] |
O(1) |
O(n) |
| 删除元素 |
O(1) |
O(n) |
| 遍历[注2] |
O(n) |
O(n) |
集合(set):
- 内部实现是dict的,在in操作上是O(1),这一点比list要强
| 操作 |
平均情况 |
最坏情况 |
| x in s |
O(1) |
O(n) |
| 并集 s\ |
t |
O(len(s)+len(t)) |
| 交集 s&t |
O(min(len(s), len(t)) |
O(len(s) * len(t)) |
| 差集 s-t |
O(len(s)) |
|
| s.difference_update(t) |
O(len(t)) |
|
| 对称差集 s^t |
O(len(s)) |
O(len(s) * len(t)) |
| s.symmetric_difference_update(t) |
O(len(t)) |
O(len(t) * len(s)) |
空间复杂度
- 是用来评估算法内存占用大小的方式,定义一个或多个变量,空间复杂度都是为1,列表的空间复杂度为列表的长度
a = 'Python' #空间复杂度为1
b = 'PHP'
c = 'Java'
num = [1, 2, 3, 4, 5] #空间复杂度为5
num = [[1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4]] #空间复杂度为5*4
num = [[[1, 2], [1, 2]], [[1, 2], [1, 2]] , [[1, 2], [1, 2]]] #空间复杂度为3*2*2