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

列表的内置操作的时间复杂度

操作	时间复杂度	解释
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