我有两个变位检测功能；一个使用排序和比较，另一个跟踪每个字母字符的出现次数。
这里假设传递给函数的两个字符串是相同的，第一个是随机生成的(未排序)，第二个=传递给第一个，这样两个函数都"一直"执行并返回True。
根据我的算法分析(显然可能是错误的…)，第一个函数应该是2*nlog(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
对于两个100000个字符的字符串，这意味着第一个函数将是340万个时间单位，而第二个函数则是400000个时间单位。
换句话说，第二个函数应该比第一个快8倍。
然而，当我对两个函数的执行进行计时时，第二个函数甚至没有第一个函数的两倍快。对于两个100000个字符的字符串，第一个函数在0.085s内执行，第二个函数在0.055s内执行。
发生了什么？
理论复杂性可能与实际花费的时间几乎没有关系。考虑：
- 单个操作的各种复杂性(例如除法与加法)
- 内存访问(由于频繁对大型阵列进行随机访问，导致缓存命中率下降，可能会将其降低到一半以上)
- 编译器/解释器优化
- 等等
并且不是每个排序都是O(n log (n))
- 计数排序、桶排序、基数排序均为
O(n)或接近
编辑：我在100M长数组上用Java实现了这两个功能。这是383毫秒对161毫秒。在10毫秒，时间几乎相等。
- 您的100k长阵列太小，无法预热优化器
- Java使用DualPivotQuickort，它在具有许多重复值(小字符基数)的数组上几乎运行
O(n)。你的语言可能使用类似的东西
并非所有基元函数都占用相同的时间。例如，第二种方法包括除法，它通常比其他操作占用更多的CPU周期。虽然第一个函数是O(n-log(n))，第二个是O(n)，但你不知道常数因子是什么
你的分析真正表明，如果你现在用一百万个字符串来做，你应该会看到速度的差异会扩大。