Python列表/字典操作 时间复杂度
Python 列表/字典操作时间复杂度
#1 环境
Python3.7.3#2 List
操作 | 操作说明 | 时间复杂度 |
|---|---|---|
index(value) | 查找list某个元素的索引 | O(1) |
a = index(value) | 索引赋值 | O(1) |
append(value) | 队尾添加 | O(1) |
pop() | 队尾删除 | O(1) |
pop(index) | 根据索引删除某个元素 | O(n) |
insert(index, value) | 根据索引插入某个元素 | O(n) iterration |
search(in) | 列表搜索（其实就是in关键字） | O(n) |
slice [x:y] | 切片, 获取x, y为O(1), 获取x,y 中间的值为O(k) | O(k) |
del slice [x:y] | 删除切片，删除切片后数据需要重新移动/合并 | O(n) |
reverse | 列表反转 | O(n) |
sort | 排序 | O(nlogn) |
#3 Dict
操作 | 操作说明 | 时间复杂度 |
|---|---|---|
copy | 复制 | O(n) |
get(value) | 获取 | O(1) |
set(value) | 修改 | O(1) |
delete(value) | 删除 | O(1) |
search(value) | 字典搜索 | O(1) |
iterration(value) | 字典迭代 | O(n) |
# 字典的特性
- 查找速度快,无论dict有10个元素还是10万个元素，查找速度都一样。而list的查找速度随着元素增加而逐渐下降。 不过dict的查找速度快不是没有代价的，dict的缺点是占用内存大，还会浪费很多内容，list正好相反，占用内存小，但是查找速度慢。
- 字典值可以没有限制地取任何python对象，既可以是标准的对象，也可以是用户定义的，但键不行。不允许同一个键出现两次。 键必须不可变，所以可以用数字，字符串或元组充当，所以用列表就不行。
- dict的第二个特点就是存储的key-value序对是没有顺序的！这和list不一样。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2019/05/18 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
