使用字典理解来计算列表中出现次数的大 O 复杂度

Question

我有数字列表

nums = [1,1,2,3,3]

并且想要创建一个包含这些数字出现次数的字典

{1:2,2:1,3:2}

如果我使用这样的字典理解来做到这一点：

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

它比循环数组并逐一增加计数慢吗？

Answer 1

nums.count()

是 O(n)，并且您调用它（最坏的情况下）是 O(n) 次，因此最终的复杂度是 O(n²)。

遍历数组并增加频率计数仅需 O(n)。