双层循环与JS内置方法查询数组公共值的时间复杂度对比疑问

1. 该写法的时间复杂度是否为O(n)？ #

不是，这个写法的理论时间复杂度仍然是O(nm)*，和双层循环没有本质区别：

• two.some会遍历two数组的元素，最坏情况遍历完整数组，时间复杂度O(n)（n为two的长度）
• 每次调用one.includes都会遍历one数组的元素，最坏情况遍历完整数组，时间复杂度O(m)（m为one的长度）
  两者相乘总复杂度为O(n*m)，和手写双层循环是同一复杂度等级。

2. 内置方法底层也是循环，为什么性能更高？ #

核心原因有两个：

• 原生方法是编译执行，JS层循环是解释执行：some、includes这类JS内置方法都是由V8等JS引擎用C/C++实现，编译为机器码直接运行，没有JS层代码的解释、类型校验、上下文切换等额外开销。哪怕逻辑和你手写的JS双层循环完全一致，执行效率也会高出数倍到数十倍。
• 默认短路优化：some方法只要找到第一个满足条件的元素就会立即终止遍历，不需要走完整个数组。如果你手写的双层循环没有加提前跳出循环的逻辑，那平均场景下内置方法的实际执行步数会少很多；哪怕你手写循环也加了break逻辑，原生方法的编译执行优势依然存在。

3. 真·O(n)复杂度的实现方案 #

如果要把时间复杂度降到O(n)级别，可以借助Set的O(1)查询特性实现：

const one = [1,2,3,4,5];
const two = [5,6,7,8];
const setOne = new Set(one);
const hasCommon = two.some(item => setOne.has(item));

这个方案先把第一个数组转成Set（复杂度O(m)），再遍历第二个数组做存在性判断（每次查询O(1)，最坏总复杂度O(n)），总复杂度为O(n+m)，数组元素量级越大，性能优势越明显。

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