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

列表的内置操作的时间复杂度 操作时间复杂度解释index x[]O(1)通过一步操作就能够定位到索引的元素，而不是遍历所有元素，这也是Python中list结构的特点：允许对元素进行快速的随机访问（即检索位于特定索引位置的元素）appendO(1)只需要一步就能在list尾部追加元素pop()O(1)移除最后一个元素，可以直接定位，一步删除pop(i)O(n)移除指定元素，最坏的情况需要全部寻找一次insert(i,item)O(n)将其他位置需要后移，最坏需要全部后移一次del listO(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)最坏情况是删除了最开始的元素，后边元素全部前移reverseO(n)每个元素需要操作一次两个列表拼接O(k)k为第二个列表的元素个数，因为需要放到第一个列表的后边sortO(nlogn)底层封装，python list底层的sort排序算法采用了Timsort排序算法，Timsort是结合了合并排序（merge sort）和插入排序（insert sort）而得出的排序算法。 字典的内置操作的时间复杂度 操作时间复杂度解释copyO(n)字典中所有元素都要复制一次ger itemO(1)类似列表的所有，可以一键定位set itemO(1)添加新值，直接操作delete itemO(1)删除值，一键定位contains(in)O(1)字典可以一步查找遍历O(n)全部元素操作一次