向Python字典中添加单词列表统计频次的最坏时间复杂度是多少

# Dictionary containing words and their frequencies
word_freq = {}

# Adding each word in the dictionary, and updating the frequency
for word in words:
    if word in word_freq:
        word_freq[word] += 1
    else:
        word_freq[word] = 1

你的推导在理论层面是正确的，不过要区分理论最坏情况和实际平均情况两种场景：

• 理论最坏情况：哈希表的插入、查询操作最坏时间复杂度为O(n)，触发条件是所有插入的单词哈希值完全冲突，都被分配到同一个哈希桶的链表中，每次查询都要遍历整个链表的所有元素，n次循环下来总时间复杂度就是O(n²)，你的推导逻辑符合这个极端场景的计算规则。
• 实际平均情况：Python内置的dict底层做了多重优化，一是针对字符串等常用类型的哈希函数设计足够合理，天然能避免绝大多数哈希冲突；二是当负载因子超过阈值时会自动扩容重哈希，进一步降低冲突概率。正常业务场景下dict的插入、查询操作平均时间复杂度为O(1)，所以这段代码的平均时间复杂度为O(n)，这也是我们日常做算法复杂度评估时默认采用的结论。

补充：只有在刻意构造哈希冲突的攻击场景下，才会触发O(n²)的最坏时间复杂度，普通开发场景完全不需要考虑这个极端情况。

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