Leetcode 347：Python前K个高频元素O(n)时间复杂度疑问

我正在研究LeetCode第347题的更高效解法，自己的解法效率较低。但我无法理解以下Python桶排序解法为何能达到O(n)时间复杂度，原代码如下（注：代码存在笔误，freq_buckets = for [[] for i in range(len(nums) + 1)]应改为freq_buckets = [[] for i in range(len(nums) + 1)]）：

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # count up the frequencies of each number: # O(n)
        counts = {}
        for n in nums:
            counts[n] = 1 + counts.get(n, 0) # add one to the count, default if not found is 0

        
        # create our buckets: O(n)
        freq_buckets = [[] for i in range(len(nums) + 1)]

        # add the counts to each of the buckets
        for num, count in counts.items():
            # for that specific frequency, add this num to the list of 
            # numbers occurring at that frequency
            freq_buckets[count].append(num)

        # hold our k most frequent
        most_frequent = []
        # iterate from most frequent to least frequent
        for i in range(len(freq_buckets) - 1, 0, -1): # O(n): loop 3
            for num in freq_buckets[i]: # O(n): loop 4
                most_frequent.append(num)

                # break when we have k most frequent
                if len(most_frequent) == k:
                    return most_frequent

我曾一度认为其时间复杂度为O(kn)，因为外层循环（loop3）似乎仅会运行至k次，但进一步分析发现外层循环与内层循环（loop4）存在平衡关系，部分场景的复杂度推导令我困惑。我是否正确认为该算法并非O(n)时间复杂度？若错误，请解释原因。我已尝试逐行分析时间复杂度，也查阅过相关帖子，但仍无法理解结论。

解答 #

这个算法确实是**O(n)**时间复杂度，原因如下：

1. 各阶段时间复杂度拆解

   • 统计频率：遍历nums数组一次，哈希表的读写操作都是O(1)，总耗时O(n)。
   • 创建桶：生成长度为n+1的空列表数组，操作次数与数组长度正相关，耗时O(n)。
   • 填充桶：遍历哈希表的所有键值对，哈希表的键数量最多为n（当所有元素都唯一时），每个元素的追加操作是O(1)，总耗时O(n)。
   • 收集结果：这里的嵌套循环容易产生误解，但核心是所有桶中的元素总数等于哈希表的键数量，最多为n。不管外层循环跑多少次，内层循环遍历的总元素数不会超过n——每个数字只会被放入一个桶中，且一旦收集到k个元素就立即终止。也就是说，这两层循环的总迭代次数是O(n)，而非O(n²)。

2. 为什么不是O(kn)
   你对外层循环的理解存在偏差：

   • 外层循环是从最高频率往下遍历，但每个桶可能包含多个元素。比如最高频率的桶里如果有k个元素，外层循环只需要跑1次就能收集到结果；即使每个桶只有1个元素，外层循环最多跑k次，内层循环每次仅迭代1次，总操作数是k，而题目中k≤n（合法输入下k不超过不同元素的数量，最多为n），所以总耗时仍为O(n)。
   • 本质上，嵌套循环的总操作数是所有桶内元素的总数，这个总数不会超过n，再加上提前终止的逻辑，实际操作数最多是k（远小于n），因此这部分的时间开销仍属于O(n)范畴。

综上，算法所有步骤的时间开销都是线性的，整体时间复杂度为O(n)。

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