欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

关于Python列表和字典内置方法的时间复杂度

程序员文章站 2022-03-30 10:13:52
列表的内置操作的时间复杂度操作时间复杂度解释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