LeetCode 1636题代码时间复杂度困惑：为何不是O(n·nlogn)？

问题背景 #

给定整数数组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·nlogn)，但工具判定为O(nlogn)，以下是具体解析：

分步时间复杂度分析 #

设数组nums的长度为n，数组中不同元素的数量为m（显然m ≤ n，最坏情况是所有元素都不同，m=n）：

1. 统计元素频率：Counter(nums)遍历数组一次，时间复杂度为O(n)。
2. 排序频率字典项：对m个键值对排序，排序算法时间复杂度为O(m log m)。最坏情况m=n，这一步为O(n log n)。
3. 构建频率分组字典：遍历m个键值对，将相同频率的元素归入同一列表，时间复杂度为O(m)。
4. 分组内元素排序：所有分组的元素总数之和等于m（每个元素仅属于一个分组）。假设每个分组的长度为k₁, k₂, ..., k_t，则k₁ + k₂ + ... + k_t = m。每个分组排序的时间是O(k_i log k_i)，总排序时间为ΣO(k_i log k_i)。
   根据数学性质，Σ(k_i log k_i) ≤ m log m（归纳法可证：合并两个分组后的排序时间(k1+k2)log(k1+k2)大于等于两个分组分别排序的时间和k1logk1 +k2logk2）。因此这部分总时间复杂度为O(m log m)，最坏情况为O(n log n)。
5. 构建结果数组：遍历每个分组，将元素重复对应频率次数加入结果，总操作次数等于数组长度n，时间复杂度为O(n)。

总时间复杂度 #

将各步骤时间复杂度相加：O(n) + O(m log m) + O(m) + O(m log m) + O(n)，合并后最坏情况为O(n log n)，与工具的判定一致。

误区解析 #

你误以为每个分组排序的时间是O(n log n)，但实际上所有分组的元素总数最多为n，且分组排序的总时间不会超过对m个元素整体排序的时间O(m log m)，远达不到O(n·nlogn)的量级。只有当每个分组的长度都是n时才会出现O(n logn)的单分组排序时间，但这种情况不可能发生（所有元素频率相同的情况下，分组长度为1，排序时间为O(1)）。

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