关于Python列表和字典内置方法的时间复杂度
程序员文章站
2024-01-18 14:58:28
列表的内置操作的时间复杂度操作时间复杂度解释index x[]O(1)通过一步操作就能够定位到索引的元素,而不是遍历所有元素,这也是Python中list结构的特点:允许对元素进行快速的随机访问(即检索位于特定索引位置的元素)appendO(1)只需要一步就能在list尾部追加元素pop()O(1)移除最后一个元素,可以直接定位,一步删除pop(i)O(n)移除指定元素,最坏的情况需要全部寻找一次insert(i,item)O(n)将其他位...
列表的内置操作的时间复杂度
操作 | 时间复杂度 | 解释 |
---|---|---|
index x[] | O(1) | 通过一步操作就能够定位到索引的元素,而不是遍历所有元素,这也是Python中list结构的特点:允许对元素进行快速的随机访问(即检索位于特定索引位置的元素) |
append | O(1) | 只需要一步就能在list尾部追加元素 |
pop() | O(1) | 移除最后一个元素,可以直接定位,一步删除 |
pop(i) | O(n) | 移除指定元素,最坏的情况需要全部寻找一次 |
insert(i,item) | O(n) | 将其他位置需要后移,最坏需要全部后移一次 |
del list | O(n) | 将list中的元素一个一个的清空 |
for循环迭代 | O(n) | 遍历一次 |
contains(in) | O(n) | 判断在不在list表中,需要遍历一次 |
切片s[x:y] | O(K) | k就代表从x到y-1位置元素的个数,首先定位到x位置,由前面index操作时间复杂度可以知道定位x位置的操作时间复杂度为O(1),定位完以后需要一取元素,取多少个元素由x到y-1之间元素个数k所决定。此时和list中元素总数n没有关系,100个元素取1:6只取5个元素,从10000个元素中取1:6也是取5个元素,因此时间复杂度和n没有关系,只与切片元素的个数有关 |
删除指定切片 | O(n) | 最坏情况是删除了最开始的元素,后边元素全部前移 |
reverse | O(n) | 每个元素需要操作一次 |
两个列表拼接 | O(k) | k为第二个列表的元素个数,因为需要放到第一个列表的后边 |
sort | O(nlogn) | 底层封装,python list底层的sort排序算法采用了Timsort排序算法,Timsort是结合了合并排序(merge sort)和插入排序(insert sort)而得出的排序算法。 |
字典的内置操作的时间复杂度
操作 | 时间复杂度 | 解释 |
---|---|---|
copy | O(n) | 字典中所有元素都要复制一次 |
ger item | O(1) | 类似列表的所有,可以一键定位 |
set item | O(1) | 添加新值,直接操作 |
delete item | O(1) | 删除值,一键定位 |
contains(in) | O(1) | 字典可以一步查找 |
遍历 | O(n) | 全部元素操作一次 |
本文地址:https://blog.csdn.net/qq_40558166/article/details/107144066
上一篇: 粉象生活联手优酷,开启扶贫新力量
下一篇: egg连接mysql数据库配置
推荐阅读
-
关于Python列表和字典内置方法的时间复杂度
-
Python中字典(dict)和列表(list)的排序方法实例
-
Python中字典(dict)和列表(list)的排序方法实例
-
Python 利用内置set函数对字符串和列表进行去重的方法
-
Python 利用内置set函数对字符串和列表进行去重的方法
-
Python中字典(dict)和列表(list)的排序方法实例
-
Python中字典(dict)和列表(list)的排序方法实例
-
关于Python列表和字典内置方法的时间复杂度
-
Python 性能测试,关于创建,遍历查询列表List,元组Tuple,集合Set,字典Dict,有序字典OrderedDict的 速度 和 空间 测试