大O复杂度更高的算法实际运行速度会更快吗？

核心前提纠正：你对两段代码的时间复杂度计算完全错误，这是你产生困惑的根本原因 #

你误以为第一段代码复杂度是O(n²)、第二段是O(n³)，但实际上你漏算了子串排序、以及大列表双层遍历的开销：

• 第一段代码实际复杂度为O(n⁴)：
  1. 首先枚举所有子串的双层循环得到的子串总数是O(n²)量级，每个子串排序的开销是O(k logk)（k为子串长度），这一步总开销已经是O(n³ logn)
  2. 最后比对所有子串的双层循环是直接遍历O(n²)量级的子串列表做两两比对，这一步的时间复杂度是O((n²)²)=O(n⁴)，是整个代码跑的慢的核心原因，n=20时这一步就要执行160万次比对，n=30时直接涨到8100万次，开销极高
• 第二段代码（注意代码存在变量名错误：anagrams未定义，应改为count）实际复杂度为O(n³ logn)：
  三层嵌套循环的总执行次数是O(n³)量级，加上每次子串排序的O(k logk)开销，总复杂度确实低于第一段代码的O(n⁴)，所以跑的更快完全符合大O表示法的预测，不存在矛盾。

关于大O表示法的可靠性说明 #

你的推导结论不成立，你的案例是复杂度计算错误导致的，不是大O表示法本身的问题：

1. 大O表示法的定义是忽略常数系数、只描述n趋近于无穷时的时间增长趋势，本身就不负责小n场景下的常数级差异对比
2. 如果两个算法的理论复杂度确实处于同一量级，只是常数系数不同，那么小n场景下可以通过实际测试判断性能；但如果理论复杂度差了一个及以上的量级（比如O(n³)和O(n⁴)），不管n多小，只要n大到能体现量级差异，高阶复杂度的代码一定会更慢。

该问题的最优解法参考 #

这个问题的标准解法是用哈希表统计同模式子串的出现次数，避免两两比对的额外开销：

1. 枚举所有子串，将排序后的子串作为哈希表的key，统计每个key出现的次数
2. 最终每个key如果出现了c次，对应的异位对数量就是c*(c-1)//2，累加所有结果即可
3. 该解法的时间复杂度为O(n² logn)，比你提供的两段代码性能都高很多。

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