关于数组交集算法最佳情况比较次数的疑问咨询

你的分析是对的：如果两个元素不重复且有序的完全相同数组（比如[1,2,3,...,N]），运行这段代码时，内层循环的比较次数会是1+2+...+N = N(N+1)/2次，确实远超过N次。

书中提到的“最佳情况仅N次比较”，特指两个数组的所有元素完全相同的场景（比如[5,5,5,...,5]）。这种情况下，外层循环的每个i对应的元素，在内层循环j=0时就会匹配成功，每次只需要1次比较就触发break，N次外层循环下来总比较次数就是N次——这才是书中定义的“最佳情况”。

如果想让任意完全相同数组的比较次数都降到O(N)，可以用哈希集合优化算法，避免嵌套循环：

function intersection(firstArray, secondArray){
    const secondSet = new Set(secondArray);
    return firstArray.filter(item => secondSet.has(item));
}

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