字母异位词分组算法时间复杂度存疑：O(n*m)为何慢于O(n*mlogm)

问题背景 #

我们需要将仅包含a、b、c、d四种字符的字符串列表中的字母异位词归为一组。例如输入["abc","acb","add","dda","ddd","aaa"]，预期输出为[['abc', 'acb'], ['add', 'dda'], ['ddd'], ['aaa']]。其中n代表输入字符串的数量，m代表单个字符串的长度。

两种实现解法 #

常规排序解法（时间复杂度O(n·mlogm)） #

该解法通过将每个字符串排序后得到的结果作为分组标识，利用字典将异位词归类：

from collections import defaultdict

def groupAnagrams(strs: list[str]) -> list[list[str]]:  # O(n * mlogm) 时间复杂度
    mapping = defaultdict(list)
    for s in strs:  # 遍历所有字符串，O(n)
        sig = "".join(sorted(s))  # 排序生成标识，O(m*logm)
        mapping[sig].append(s)
    return list(mapping.values())

print(groupAnagrams(["abc","acb","add","dda","ddd","aaa"]))

字符计数优化解法（时间复杂度O(n·m)） #

该解法通过统计每个字符串中a、b、c、d的出现次数，将计数结果转为元组作为分组标识，理论上时间复杂度更低：

from collections import defaultdict

def groupAnagrams2(strs: list[str]) -> list[list[str]]:  # O(n * m) 时间复杂度
    res = defaultdict(list)
    for s in strs:  # 遍历所有字符串，O(n)
        count = [0]*4
        for c in s:  # 统计每个字符出现次数，O(m)
            count[ord(c) - ord("a")] += 1
        res[tuple(count)].append(s)  # 用计数元组作为键，O(4)
    return list(res.values())

print(groupAnagrams2(["abc","acb","add","dda","ddd","aaa"]))

实测性能结果 #

小列表测试 #

groupAnagrams(["abc","acb","add","dda","ddd","aaa"]) -> 2.21 µs ± 23.8 ns per loop (7次运行的均值±标准差，每次100,000循环)
groupAnagrams2(["abc","acb","add","dda","ddd","aaa"]) -> 3.02 µs ± 18.1 ns per loop (7次运行的均值±标准差，每次100,000循环)

大列表测试 #

测试代码：

import random
random_strings = ["".join([chr(random.randint(97, 100)) for _ in range(100000)]) for _ in range(1000)]

测试结果：

groupAnagrams(random_strings) -> 5.48 s ± 33 ms per loop (7次运行的均值±标准差，每次1循环)
groupAnagrams2(random_strings) -> 7.13 s ± 83.5 ms per loop (7次运行的均值±标准差，每次1循环)

原因分析 #

虽然从渐近时间复杂度来看，O(n·m)的计数解法应该更优，但实际测试中排序解法更快，核心原因在于底层实现的效率差异和常数因子的影响：

1. 排序函数的底层优化：Python的sorted()函数基于Timsort算法实现，且完全由C语言编写，执行效率极高。即使时间复杂度带logm，C级别的循环和排序操作比Python层的循环快几个数量级。
2. Python循环的开销：计数解法中需要在Python层遍历每个字符，执行ord(c)计算、数组索引访问、自增操作等，这些纯Python操作的单步开销远大于C实现的排序步骤。即使m达到100000，排序的总开销依然低于Python循环的总开销。
3. 哈希键的生成与查找效率：排序解法生成的字符串作为字典键，Python对字符串的哈希和字典查找有专门的优化；而计数解法生成的长度为4的元组，在哈希计算和字典访问上并没有明显优势，甚至略逊于字符串。
4. 字符集大小的放大效应：本次问题中字符集仅包含4个字符，Timsort在处理小范围元素时会进一步优化排序效率；而计数解法无论字符集大小如何，都需要遍历每个字符统计次数，无法利用字符集小的优势减少操作量。如果字符集扩大到26个甚至更多，计数解法的优势才会逐渐显现，但在本场景下排序解法的优势被放大。

内容的提问来源于stack exchange，提问作者FluidMechanics Potential Flows