Python列表内置count等方法的时间复杂度是O(1)还是O(n)?
Python列表内置方法时间复杂度解答
核心问题结论:count方法的时间复杂度
Python列表底层基于动态数组实现,内置count()方法的底层逻辑为遍历全量元素逐一匹配目标值、统计匹配次数,时间复杂度为O(n),和你自行编写的Python层循环统计的时间复杂度等级完全一致。
二者仅存在实现层的性能差异:内置count()由C语言实现,避开了Python解释器执行循环的额外开销,实际运行速度远快于手写Python循环,但时间复杂度等级没有区别。
常用列表内置方法时间复杂度汇总
count(x):O(n),n为列表总长度,需要遍历所有元素完成匹配统计index(x):O(n),从列表头部开始遍历查找第一个匹配元素的位置,最坏情况需要遍历全表reverse():O(n),原地交换首尾对应位置的元素,需要遍历半数元素,复杂度等级为O(n)append(x):O(1)(均摊复杂度),仅在列表容量不足需要扩容时才会复制全量元素,绝大多数场景下为常数级开销pop():O(1),仅弹出列表尾部元素,无需移动其他元素pop(i)/insert(i, x):O(n),在指定位置插入/删除元素时,需要移动该位置之后的所有元素腾出空间sort():O(n log n),底层采用Timsort算法,平均和最坏时间复杂度均为n log nx in list成员判断:O(n),需要遍历列表逐一匹配元素- 切片操作
list[a:b]:O(k),k为切片的长度(即b-a),需要复制对应数量的元素生成新列表
两种统计元素出现次数的实现代码
调用count方法实现
List1 = [10,4,5,10,6,4,10] print(List1.count(10))
手写循环遍历实现
List2 = [10,4,5,10,6,4,10] count = 0 for ele in List2: if ele == 10: count += 1 print(count)
内容的提问来源于stack exchange,提问作者user13952262
相关产品推荐
相关产品推荐

