algorithm - (2n log(n) + n) 变位词检测函数并不比 4n + 26 函数慢多少，尽管 n 很大

Question

我有 2 个字谜检测功能；一个使用排序和比较，另一个跟踪每个字母字符出现的次数。

这里假设传递给函数的两个字符串是相同的，第一个随机生成(未排序)，第二个 = 给第一个，这样两个函数都“一路”执行并返回 True。

根据我的算法分析(显然可能是错误的...)，第一个函数应该是 2 * n log(n) + n，第二个函数是 2 + 2n + 2n + 26 = 28 + 5n。

def anag1(s1, s2):      
    s1 = list(s1)
    s1.sort()
    s2 = list(s2)
    s2.sort()

    for i in range(len(s1)):
        if s1[i] != s2[i]:
            return False

    return True

def anag2(s1, s2):
    l1 = [0] * 26
    l2 = [0] * 26
    for i in s1:
        k = ord(i) % 26
        l1[k] += 1
    for i in s2:
        k = ord(i) % 26
        l2[k] += 1

    return l1 == l2

对于 2 个 100,000 个字符的字符串，这应该意味着第一个函数将是 340 万个时间单位，而第二个函数是 400,000 个时间单位。

换句话说，第二个函数应该比第一个快将近 8 倍。

但是，当我对这两个函数的执行进行计时时，第二个甚至没有第一个快两倍。对于 2 个 100,000 个字符的字符串，第一个函数在 0.085 秒内执行，第二个在 0.055 秒内执行。

发生了什么？

Answer 1

理论复杂度可能与实际花费的时间关系不大。考虑:

• 单一操作的各种复杂性(例如除法与加法)
• 内存访问(由于对巨大数组的频繁随机访问导致缓存命中率低，可能会减慢一半以上)
• 编译器/解释器优化
• 等等

并不是每一种排序都是O(n log (n))

• 计数排序、桶排序、基数排序都是O(n)或接近。

编辑:我在 100M 数字长数组上用 Java 实现了这两个。这是 383 与 161 毫秒。在 10M 上，时间几乎相等。

• 您的 100k 长数组太小，无法预热优化器。
• Java 使用 DualPivotQuickSort，它在具有许多重复值(小字符基数)的数组上运行几乎 O(n)。您的语言可能使用类似的东西。