Top K高频元素代码复杂度判定：k为常数时是否为O(M)

1. 常数循环与M规模循环嵌套的时间复杂度判断 #

大O表示法会省略所有常数系数，仅保留和输入规模相关的增长项，因此两种情况对应不同结果：

• 如果循环次数k是和输入规模完全无关的固定常数，嵌套循环的整体时间复杂度为O(M)
• 如果k是和输入规模相关的变量（例如k随M增长、k等于M等），嵌套循环的整体时间复杂度为O(kM)

2. 前K个高频元素代码分析 #

你贴出的代码如下：

from collections import defaultdict
from typing import List

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        my_dict = defaultdict(int)
        top_two_final = []

        for i in range(len(nums)):
            my_dict[nums[i]] += 1

        sorted_values = sorted(my_dict.values(), reverse=True)

        for j in my_dict:
            for l in sorted_values[:k]:
                if my_dict[j] == l:
                    top_two_final.append(j)

        return set(top_two_final)

时间复杂度分析 #

你的原有分析遗漏了排序步骤的开销，完整的时间复杂度拆解如下：

• 遍历数组统计频率：O(M)，M为nums数组长度
• 对频率值排序：假设不同元素的数量为N（N≤M），排序开销为O(N log N)，最差情况所有元素都不同，这部分开销为O(M log M)
• 后续双层循环：外层遍历N个不同元素，内层遍历k个高频频率值，开销为O(Nk)，最差情况为O(Mk)

整体时间复杂度为O(M log M + Mk)。
如果k为常数，O(Mk)确实可以简化为O(M)，但排序步骤的O(M log M)是更高阶的开销，因此整体时间复杂度还是O(M log M)，无法达到O(M)。

另外补充代码存在的问题：如果存在多个元素频率相同且落入前k个频率区间，你返回的set长度会超过k，不符合题目要求；且sorted_values[:k]存在重复频率值时，同一个元素会被多次加入结果列表，产生无用开销。

空间复杂度分析 #

你原有判断O(Mk)是错误的，空间复杂度统计的是额外占用的存储空间峰值，你的代码里没有和M、k乘积相关的存储开销：

• 频率字典最大占用O(M)
• 排序后的频率数组最大占用O(M)
• 结果列表最大占用O(M)

因此整体空间复杂度为O(M)，和k是否为常数无关。

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