为何O(n²)最长无重复子串算法比O(n)实现更快？

这看起来是个反直觉的结果，但其实是渐近复杂度的理论模型和实际运行环境的细节之间的差异导致的，具体可以从这几个角度理解：

1. 渐近复杂度不代表实际常数开销 #

时间复杂度的O标记描述的是n趋近于无穷大时的增长趋势，但它忽略了每个操作的常数开销，而这个开销在实际运行中可能会主导性能：

• 你的朴素算法虽然是嵌套循环，但因为测试用的是只有26个字母的随机字符串，内层循环几乎每次走不了几步就会遇到重复字符，直接break退出。平均下来，内层循环的迭代次数大概只有26次左右，实际总操作次数是n*26，和O(n)的量级几乎一致。
• 滑动窗口算法的哈希表（seen对象）操作虽然是理论上的O(1)，但它的常数开销远高于朴素算法里的数组遍历：哈希函数计算、哈希冲突的处理、对象属性的动态存取，每一步都比数组的简单比较要消耗更多CPU周期。

2. 数据局部性带来的缓存优势 #

CPU的高速缓存（L1/L2/L3）对性能的影响极大，你的朴素算法在这方面占了很大便宜：

• 你把字符串转成数组后，内层循环是在数组的连续片段上遍历，而且letterArray最多只有26个元素，这些数据都能轻松被CPU缓存命中，缓存访问速度比主存快几十到上百倍。
• 滑动窗口里的seen对象是哈希表结构，它的键值对在内存中是散列存储的，不是连续的，CPU很难把这些数据缓存起来，每次存取都要从主存读取，开销极高。

3. JavaScript引擎的JIT优化偏向 #

V8等JavaScript引擎对不同操作的优化程度差异很大：

• 你的朴素算法里的数组push、find操作都是引擎高度优化的热点操作，尤其是find在26元素的小数组上，JIT编译器甚至可能把它优化成一系列直接的比较语句，完全没有循环开销。
• 滑动窗口里的动态对象属性存取（seen[char]），因为键是随机的字符串，引擎很难做静态优化，哈希表的操作也没有太多优化空间，执行效率自然不如数组操作。

验证：换个测试用例就会现原形 #

如果把测试用的字符串换成几乎无重复的长字符串（比如用包含上千个不同字符的字符集生成），你的朴素算法的内层循环就会几乎遍历到字符串末尾，这时它的O(n²)复杂度就会显现出来，运行时间会呈指数级增长；而滑动窗口算法仍然保持O(n)的性能，这时就能看出两者的真实差距。

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