使用JavaScript中的filter()函数在两个未排序数组中查找交集的时间复杂度

Question

我刚开始学习大 O 表示法，试图理解不同函数的时间复杂度，以确定哪个更好。

我在计算以下代码的时间和空间复杂度方面遇到了困难。

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

  findCommonElem(arr1, arr2);

据我所知，常见的数组方法如filter()通常具有O(n)的时间复杂度，因此在这种情况下，它将取决于每个数组的长度而成为O(m+n)。不过，我的理解可能是错误的。

能否有人解释一下？非常感谢！

额外问题：与对同一函数使用while循环排序数组相比，哪一个被认为是“更好的”呢？

- supvicky

---

为什么是 m + n？findCommonElem 函数在最坏情况下会将 arr1 的每个元素与 arr2 的每个元素进行比较 -> m * n。 - Andreas

这不是O(m * n)吗？ - radulle

由于数组过滤函数必须遍历所有条目，数组包含函数也是如此。复杂度将为O(m*n)。 - Ahmad Suddle

非常感谢你们的快速回复，@Andreas和@radulle！这确实有道理。就像我之前提到的，我可能完全错了哈哈，所以感谢你们的纠正！:) - supvicky

你有没有考虑数组的顺序对结果产生影响呢？如果arr2比arr1更大，那么应该将过滤器应用于arr2，并使用arr1进行includes()测试。 - ATD

Answer 1

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

但是，你能让这个解决方案更有效率吗？

可以。你可以将其简化为 O(M + N)。

TLDR：使用哈希表实现线性时间复杂度 O(M + N)。

---

方法1

检查数组1的每个元素与数组2的每个元素。(这是你正在使用的方法。)

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。

• 空间复杂度 = O(M) 或者 O(N)

  • 最多只有一个数组的所有元素可以在交集中。

方法2

使用哈希映射来线性化嵌套循环。首先，用数组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];

上述函数返回相同的结果。但有一个区别 - 嵌套循环被简化为两个线性循环，对于数组而言。这意味着两个数组只被遍历一次。

• 时间复杂度 = O(M + N)

  • 数组1被遍历一次（M个元素）。
  • 数组2被遍历一次（N个元素）。
  • 使用map.has()检查映射中是否包含元素只需要常量时间O(1)。
  • 总运行时间 = M + N

• 空间复杂度 = O(M) 或者 O(N)

  • 这里空间复杂度仍然相同，因为新哈希映射所需的空间为O(M) 或者 O(N)。我们的中间数组占用的空间也是O(M) 或者 O(N)，依然相同。

Bonus: 不了解哈希映射内部工作原理？观看此视频。

方法3

使用set代替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];

这种方法使用的空间较少，但TC和SC的算法复杂度仍然相同。

• 时间复杂度 = O(M + N)
• 空间复杂度 = O(M) 或 O(N)

感谢Nick Parsons指出这一点。

- kabirbaidhya

Answer 2

假设arr1.length为n，arr2.length为m。所以对于arr1中的每个项目，filter函数运行了您编写的lambda函数。Lambda函数检查一个项目是否在arr2中，如果在最坏情况下没有找到该项，则函数在整个数组上运行了m次。因此，arr1.filter(x => arr2.includes(x)) 的最坏情况时间复杂度为O(n*m)。

至于空间复杂度，filter函数创建一个新数组，在最坏的情况下该数组大小与原始数组一样大，所以空间复杂度为O(n)。

- Saar Davidson

Answer 3

正如它所正确提到的，这里的大O将等于 O(n*m)，这是一个解释：

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

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

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

我认为我无法回答排序问题，因为我没有清楚地理解您的意思。

- Anton Kononenko

---

复杂度是O(n)也是对的，只有当n >= m时才成立。更准确地说，可以说"arr2.includes的复杂度是O(m)"。 - Nick Parsons

谢谢你的回答！针对我的上一个问题，我正在与下面的代码进行比较。如果我将arr2替换为Set，性能是否超过下面展示的排序方法？`function findCommonElem(arr1, arr2) { arr1.sort((a, b) => a - b); //O(n log n) arr2.sort((a, b) => a - b); //O(m log m) let result = []; let i = 0, j = 0; while (i < arr1.length && j < arr2.length) { if (arr1[i] == arr2[j]) { result.push(arr1[i]); i++; j++; } else if (arr1[i] < arr2[j]) { i++; } else { j++; } } //(O(m+n)) console.log(result); }` - supvicky

@supvicky 这段代码的时间复杂度可以更好。实际上，它应该是 O(n log(n) + m log(m))。 - Saar Davidson