Python中从列表构建元素频率字典的时间复杂度是多少

你给出的示例代码如下：

freq = {}
for ele in ls:
    if ele in freq:
        freq[ele] += 1
    else:
        freq[ele] = 1

时间复杂度结论 #

• 平均时间复杂度：O(n)，n为输入列表的元素总数，这是绝大多数场景下的实际复杂度
• 最坏时间复杂度：O(n²)，仅在极端哈希冲突场景下触发，日常开发几乎不会遇到

推导依据 #

Python的字典底层是哈希表实现：

1. 外层需要遍历整个列表的所有元素，固定执行n次循环迭代
2. 每次循环内的ele in freq成员判断、字典读/写操作，平均情况的时间复杂度都是O(1)：哈希表通过计算键的哈希值直接定位存储位置，不需要遍历所有已存储的键
3. 只有当所有元素的哈希值完全一致，哈希表退化为链表结构时，单次字典操作的复杂度会升高到O(k)（k为当前字典已存储的元素数量），累加后整体复杂度才会达到O(n²)。Python内置的哈希算法对整数、字符串等常用类型做了碰撞规避优化，普通业务场景下不会出现该极端情况。

内容的提问来源于stack exchange，提问作者Aadi