Python中Top K频繁元素的时间复杂度(Leetcode)

Question

我正在尝试理解Leetcode上第347题的一个更高效的解决方案。我的解决方案效率不高。我不明白为什么这个解决方案的运行时间是O(n)。

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 [[] 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)，因为循环3只会运行到k。但是，经过进一步检查，我发现循环3和循环4之间有一种平衡关系，因为如果外层循环运行了n次，那么内层循环可能会运行0到n + 1次。这让我相信，如果内层循环运行了n次，那么我们一定是在1的桶里，这意味着我们几乎已经在外层循环中迭代了n次，然后再在内层循环中迭代k次（如果n = k，那么k也可能等于n）。

有些情况我很难理解。我是不是可以认为这个算法的运行时间不是O(n)？如果不是，请解释一下原因。

我尝试分析每一行的时间复杂度，期望能找到O(n)。

我还阅读了另一篇帖子这里，但不明白他们是如何得出结论的。

Answer 1

每次内层循环都会往 most_frequent 这个列表里添加一个元素。一旦这个列表的大小达到了 k，函数就会停止。此外，most_frequent 并不会在外层循环每次加1的时候就重置。所以，内层循环最多只会运行 k 次，无论外层循环运行了多少次。

对这个过程进行复杂度分析，结果是 O(N+K)——外层循环的复杂度是 N，内层循环的复杂度是 K。因为 K 的值总是小于等于 N，所以这可以简化为 O(2N) ~ O(N)。

这里的关键点是，内层循环并不是在外层循环的每一次迭代中都运行 k 次。内层循环在所有外层循环的迭代中，总的运行次数是被一个常数 k 限制的。