理解嵌套排序的时间复杂度

Question

我正在解决这个LeetCode问题1636。按频率增加对数组进行排序:

给定一个整数数组

nums

，根据值的频率按递增顺序对数组进行排序。如果多个值具有相同的频率，则按递减顺序对它们进行排序。

返回已排序的数组。

我编写了以下工作代码：

class Solution:
    def frequencySort(self, nums: List[int]) -> List[int]:
        ddict = Counter(nums)
        ddict = dict(sorted(ddict.items(), key=lambda x:(x[1], x[0])))

        defDict = defaultdict(list)
        res = []
        for k, v in ddict.items():
            defDict[v].append(k)
        
        del(ddict)
        for k, v in defDict.items():
            v.sort(reverse=True)
            for val in v:
                for _ in range(k):
                    res.append(val)

        return res

我认为它的时间复杂度为 O(n.(nlog(n))，因为我在最坏情况下对每个键的

defaultdict

中的每个列表进行排序。

但是LeetCode中的时间复杂度分析以及chatGPT和Perplexity AI等AI工具发现时间复杂度为O(nlog(n))。我很困惑。谁能帮我理解为什么它不是 O(n.(nlog(n))？

Answer 1

对不同的数据块进行排序仍然需要 O(𝑛log𝑛)。例如，假设您在

defDict

中有 𝑘 键，其中每个键都有一个平均长度为 𝑛/𝑘 的列表 (

v

)，那么对这些

v

中的每一个进行排序将相当于 O( 𝑘 (𝑛/𝑘)log(𝑛/𝑘))，即 O(𝑛log(𝑛/𝑘))，不比 O(𝑛log𝑛) 差。