在 JavaScript 中使用 filter() 查找两个未排序数组的交集的大 O

Question

我刚开始学习大O表示法，我正在尝试了解不同函数的大O，看看哪个更好。

我正在努力计算以下代码的时间和space复杂度。

function findCommonElem(arr1, arr2) { 
  let result = arr1.filter(x => arr2.includes(x));
  console.log(result);
}

  findCommonElem(arr1, arr2);

据我了解，像 filter() 这样的常见数组方法通常有一个很大的 O O(n) 所以在这种情况下，它会是 O(m+n) 取决于每个的长度大批。但是，我可能大错特错了。

有人可以解释一下吗？非常感谢！

附加问题：与对数组排序然后对同一函数使用 while 循环相比，哪个会被认为“更好”？

Answer 1

假设 arr1.length 是 n，arr2.length 是 m。所以 filter 函数运行您为 arr1 中的每个项目编写的 lambda 函数。 lambda 函数检查一个项目是否在 arr2 中，在最坏的情况下它没有找到它运行在所有数组上的函数 m 次。因此 arr1.filter(x => arr2.includes(x)) 运行在最坏的情况下 O(n*m).

至于 space 复杂度，filter 函数创建一个新数组，在最坏的情况下，数组大小与原始数组一样大，因此 space 复杂度为 O (n)

Answer 2

正如它正确提到的，这里的大 O 等于 O(n*m)，这里是对此的解释：

arr1.filter 复杂度为 O(n)
arr2.includes 复杂度也是 O(n)

然而，对于 .filter 中的每次迭代，您每次都执行 arr2.includes，这会导致 O(n) * O(n) = O(n * m)

如果将 arr2 替换为 JS Set，您可能会提高性能。 JS Set.has 复杂度为 O(1)，因此使用 Set 而不是 arr2 应该可以帮助您实现 O(n) 复杂度。

我想我无法回答排序问题，因为我没有弄清楚你的意思。

Answer 3

上述函数的时间复杂度为O(M * N)。

但是，你能使这个解决方案更有效率吗？是的。您可以将其减少到 O(M + N).

TLDR - 使用散列table实现线性时间复杂度O(M + N)

让我们看看。

方法一

用数组 2 的每个元素检查数组 1 的每个元素。（这是您正在使用的方法。）

function findCommonElem(arr1, arr2) {
  return arr1.filter(x => arr2.includes(x));
}

const arr1 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const arr2 = [2, 4, 6, 8, 10, 12, 14, 16, 20];

console.log(findCommonElem(arr1, arr2)); // [2, 4, 6, 8, 10];

时间复杂度=O(M * N)
- 在最坏的情况下，数组 1 中的每个元素都与数组 2 中的每个元素进行检查。所以，它是 M * N.
Space 复杂性 = O(M) 或 O(N)
- 至多，任一数组中的所有元素都可以在交集中。

方法 2

使用 hash map 线性化嵌套循环。首先，用数组 1 元素填充散列映射。然后使用地图检查数组 2 以找到交点。

function findCommonElem(arr1, arr2) {
  const map = new Map();

  arr1.forEach(item => map.set(item, true));

  return arr2.filter(item => map.has(item));
}

const arr1 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const arr2 = [2, 4, 6, 8, 10, 12, 14, 16, 20];

console.log(findCommonElem(arr1, arr2)); // [2, 4, 6, 8, 10];

以上函数returns输出相同。但不同之处在于 - 嵌套循环减少为数组的两个线性循环。这意味着两个数组只被遍历一次。

时间复杂度=O(M + N)
- 数组1遍历一次（M个元素）
- 数组2遍历一次（N个元素）
- 检查地图是否包含具有 map.has() 的元素需要常数时间 O(1)。
- 总运行时间 = M + N
Space 复杂性 = O(M) 或 O(N)
- Space 复杂性在这里仍然相同，因为新哈希映射所需的 space 是 O(M) 或 O(N)。我们的中间数组采用 O(M) 或 O(N)。还是一样。

奖励： 不太了解散列映射的内部工作原理？观看 this.

方法 3

使用set instead of map。集合数据结构最适合此用例，因为您不需要方法 2 中的映射值（true 值）。

function findCommonElem(arr1, arr2) {
  const set = new Set(arr1);

  return arr2.filter(item => set.has(item));
}

const arr1 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const arr2 = [2, 4, 6, 8, 10, 12, 14, 16, 20];

console.log(findCommonElem(arr1, arr2)); // [2, 4, 6, 8, 10];

这使用相对较少 space 但 TC 和 SC 的算法复杂度仍然相同。

时间复杂度=O(M + N)
Space 复杂性 = O(M) 或 O(N)

感谢 Nick Parsons 指出这一点。

在 JavaScript 中使用 filter() 查找两个未排序数组的交集的大 O

Big O of Finding the Intersection in two Unsorted Arrays Using filter() in JavaScript

javascript

arrays

big-o

time-complexity

方法一

方法 2

方法 3