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

Question

我刚开始学习大 O 符号，我正在尝试了解不同功能的大 O，看看哪个更好。

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

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

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

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

TLDR - 使用哈希表实现线性时间复杂度 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)

  • 在最坏的情况下，使用数组 2 的每个元素检查数组 1 中的每个元素。所以，它是 M * N。

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

  • 至多，来自任一阵列之一的所有元素都可以在交集中。

方法二

使用哈希映射将嵌套循环线性化。首先，用数组 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)。这仍然是一样的。

奖励：不太了解哈希映射在内部是如何工作的？看这个。

方法三

使用set而不是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)或O(N)

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