用字典推导式统计列表元素出现次数：时间复杂度与循环计数效率对比

是的，用字典推导式结合nums.count(n)的方式确实比遍历数组逐个累加计数慢很多。

原因分析 #

1. 时间复杂度差异

   • 逐个累加的方法（示例代码）：

     cnt_dict = {}
     for n in nums:
         cnt_dict[n] = cnt_dict.get(n, 0) + 1
     

     只需要遍历数组一次，每个元素的字典存取操作都是O(1)，整体时间复杂度为O(n)（n是数组长度）。

   • 字典推导式+count的方法：

     cntDict = {n:nums.count(n) for n in set(nums)}
     

     首先set(nums)需要遍历数组一次（O(n)），然后对每个唯一元素，nums.count(n)会再次遍历整个数组统计次数。假设数组中有k个唯一元素，整体时间复杂度为O(n + k*n)，最坏情况（所有元素都唯一）会达到O(n²)，性能差距会随数组规模增大而急剧扩大。

2. 实际遍历次数对比
   拿你给出的nums = [1,1,2,3,3]举例：

   • 逐个累加：只需要遍历5次；
   • 推导式方法：先遍历5次生成集合，再对3个唯一元素各遍历5次，总共5 + 3*5 = 20次，是前者的4倍。如果数组规模扩大到10000个元素，差距会变得无法忽略。

更优的替代方案 #

Python标准库的collections.Counter是专门做这类统计的工具，它底层采用类似逐个累加的实现逻辑，且是C语言优化过的，效率和手动遍历相当甚至更高，写法也更简洁：

from collections import Counter
cnt_dict = Counter(nums)

内容的提问来源于stack exchange，提问作者Tomáš Šíma