You need to enable JavaScript to run this app. Python列表内置count等方法的时间复杂度是O(1)还是O(n)?
优惠活动
大模型
产品
解决方案
定价
更多

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 n
  • x 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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.15 13:06:03