时间戳

首页 > 解决方案 > 在 JavaScript 中使用 filter() 查找两个未排序数组中的交集的大 O

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

问题描述

我刚开始学习大 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 循环相比，哪一个会被认为“更好”？

标签： javascriptarraystime-complexitybig-o

解决方案

上述函数的时间复杂度为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)或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)or O(N)。这仍然是一样的。

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

方法 3

使用set而不是map。set 数据结构最适合此用例，因为您不需要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)

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

推荐阅读