循环的大 O 与解决问题的 javascript 方法

Question

查找两个数组是否包含相似的属性或值。

const one =[1,2,3,4,5]
const two = [5,6,7,8]

// a double loop that solves this problem 
O(n^2)

VS

two.some(item => one.includes(item))
// this is more efficient than the double loop method 
// but behind the scenes isnt javascript just looping ?
// why is this more performant ? 
// and is the big O  of this O(n)?

Answer 1

如果你

a double loop that solves this problem

一旦找到匹配项就跳出循环，那么这两种方法同样效率低下——它们都需要迭代所有 N 个元素 M 次，最坏的情况，其中 N 是一个数组的长度，并且M是另一个的长度。（因此，O(n * m) 或 O(n^2)，具体取决于您希望如何指定输入的长度。）

第二种方法的优势

two.some(item => one.includes(item))

是它比使用 for 循环更可读多了。它不是更高效 - 恰恰相反，for 循环通常比数组方法更快。

如果您想将复杂度降低到 O(n)，而不是在循环内迭代第二个数组，而是在循环内使用 Set 查找，这样会快得多：

const oneSet = new Set(one);
return two.some(item => oneSet.has(item));

因为 - 导致整体复杂度为 O(n)。

循环的大 O 与解决问题的 javascript 方法

Big O for a loop vs a javasccript method that solves a problem

javascript

algorithm

big-o

data-structures