理解嵌套排序的时间复杂度：LC Daily EASY

Question

我为这个简单的leetcode问题编写了这段代码：https://leetcode.com/problems/sort-array-by-increasing-Frequency/?envType=daily-question&envId=2024-07-23

我假设它有

O(n.(nlog(n))

TC，因为我在最坏情况下对每个键的 defaultdict 中的每个列表进行排序。 但 Leetcode 中的 TC 分析以及 CHATGPT 和 Perplexity AI 等 AI 工具表示 TC 是

O(nlog(n))

。我完全困惑了。谁能帮我理解为什么不是

O(n.(nlog(n))

？

代码：

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

Answer 1

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

defDict

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

v

)，那么对这些

v

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