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

我刚刚开始学习 Big O 表示法，我试图理解不同函数的 Big O，看看哪个更好。

我正在努力计算时间和空间复杂度对于以下代码。

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

  findCommonElem(arr1, arr2);

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

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

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

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

但你能让这个解决方案更高效吗？

是的。您可以将其减少到O(M + N).

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

方法一

检查数组 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) or O(N)

  • 最多，任一数组中的一个的所有元素都可以位于交集内。

方法2

Use a hash map https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/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];

上述函数返回相同的输出。但区别就在这里——数组的嵌套循环减少为两个线性循环。这意味着两个数组仅被遍历一次。

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

  • 数组 1 被遍历一次（M 个元素）。
  • 数组 2 被遍历一次（N 个元素）。
  • 检查地图是否包含以下元素map.has()需要恒定的时间O(1).
  • 总运行时间 = M + N

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

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

Bonus:不太了解哈希映射内部如何工作？手表this https://www.youtube.com/watch?v=shs0KM3wKv8.

方法3

Use set https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set代替map https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map。设置数据结构最适合此用例，因为您不需要映射值（true值）在方法 2 中。

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) or O(N)

感谢尼克·帕森斯指出了这一点。