求解topKFrequent函数时间复杂度：分析F与N的增长关系

问题描述 #

我实现了一个topKFrequent函数，输入整数列表nums，返回其中k个出现频率最高的元素。函数代码如下：

def topKFrequent(self, nums: List[int], k: int) -> List[int]:
    freqs = {} # num:freq
    # time complexity of this loop is O(N), where N is the size of nums
    # space complexity of this loop is O(N)

    for num in nums:
        if num in freqs:
            freqs[num] += 1
        else:
            freqs[num] = 1

    # this loop has the same time and space complexity as the previous one
    inverse_freqs = {} #freq:num
    for num in freqs.keys():
        if freqs[num] in inverse_freqs:
            inverse_freqs[freqs[num]].append(num)
        else:
            inverse_freqs[freqs[num]] = [num]

    sorted_freqs = list(inverse_freqs.keys())
    # this sort is the part which I don't understand
    sorted_freqs.sort()
    l = []
    i = 0
    #these 2 loops together are O(N)
    while len(l) < k:
        for most_freq_element in inverse_freqs[sorted_freqs[-i-1]]:
            l.append(most_freq_element)
        i += 1
    return l          

我已经分析出各部分复杂度，其中排序步骤的时间复杂度为O(F * log F)，F为不同频率的数量。当nums为[1,2,2,3,3,3,...]这类序列时，sorted_freqs的规模与N的比例最大。我想知道F相对于N的增长规律，从而计算函数的整体时间复杂度。

解答 #

F的最大可能规模 #

你说的那种[1,2,2,3,3,3,...]序列，对应的频率是1、2、3……一直加到m，总和刚好等于N。用等差数列求和公式m(m+1)/2 ≈ N，算下来m大概是sqrt(2N)——也就是说这种极端情况下，F的最大值是O(sqrt(N))。

整体时间复杂度 #

把F = O(sqrt(N))代入排序步骤的复杂度，得到排序时间是O(sqrt(N) * log sqrt(N))，化简后就是O(sqrt(N) * log N)。而函数里其他步骤都是O(N)级别的，显然O(N)的量级比O(sqrt(N)*logN)大，所以整个函数的时间复杂度由O(N)主导，最终整体复杂度是O(N)。

补充说明：常规场景里F的规模会比sqrt(N)小很多，比如元素重复率高的时候F可能是常数，但复杂度分析得看最坏情况，这里最坏情况的排序开销也没超过O(N)，所以整体还是O(N)。

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