时间复杂度更高却更快？两种变位词检测函数的性能疑问

我有两个用于检测单词word1和word2是否为变位词的函数（注：若可通过重排一个单词的字母得到另一个，则二者为变位词）：

第一个函数（理论O(n)时间复杂度） #

def is_anagram(word1, word2):
    histogram = {}
    for char in word1:
        histogram[char] = histogram.get(char, 0) + 1
    # 用第二个单词消耗直方图中的计数
    for char in word2:
        histogram[char] = histogram.get(char, 0) - 1
    for vals in histogram.values():
        if vals != 0: return False
    return True

这个函数包含3个循环，理论时间复杂度为O(n)。

第二个函数（理论O(nlogn)时间复杂度） #

def is_anagram2(word1, word2):
    sorted_word1 = ''.join(sorted(word1))
    sorted_word2 = ''.join(sorted(word2))
    return sorted_word1 == sorted_word2

其中sorted函数的时间复杂度为O(nlogn)，因此该函数的理论时间复杂度为O(nlogn)。

但通过IPython的timeit命令测试执行时间后发现，is_anagram2函数的运行速度反而更快，原因如下：

• 底层实现差异：Python内置的sorted函数是用C语言实现的，执行效率远高于Python层面的循环操作。哪怕理论复杂度更高，但C代码的执行速度比Python解释器处理循环、字典操作快得多。
• 字典操作的额外开销：第一个函数里的字典histogram涉及多次get、赋值操作，这些操作在Python中都有性能损耗——比如哈希计算、键的查找、动态扩容等，累加起来的开销会超过排序的额外复杂度成本。
• 常数因子的影响：时间复杂度忽略了常数因子，但实际运行中，O(n)的常数因子可能很大，而O(nlogn)的常数因子极小。对于常见的单词长度（比如几十到几百个字符），nlogn的实际计算量加上C实现的优势，会比Python循环+字典操作更快。
• 内存与缓存友好性：排序操作的内存访问模式更连续，CPU缓存命中率更高；而字典的哈希表是随机访问模式，更容易出现缓存失效，进一步拉低执行效率。

内容的提问来源于stack exchange，提问作者AK-CHP