javascript - 这个函数的运行时复杂度是多少？

Question

我相信它是二次 O(n^2) 但不是 100% 确定，因为 .filter() 和 .map() 操作如何工作的不确定性JavaScript。

我的一个大问题是整个 filter() 操作是否在开始单个 map() 操作之前完成，或者它是否足够智能以执行 map() 操作，同时它已经在 filter() 操作中迭代。

方法

function subscribedListsFromSubscriptions(subscriptions: Subscription[]) {
    return new Set(listSubscriptions.filter((list) => {
        return list.subscribed;
      }).map((list) => {
        return list.list_id;
  }));
}

示例输入数据

let subscriptions = [ {
  list_id: 'abc', 
  subscribed: false
}, {
  list_id: 'ghi',
  subscribed: false
}];

据我所知

看起来是:

• filter() 用于 subscriptions 的每个元素 - 时间 n
• map() 用于每个剩余元素 - 时间 n(最大)
• new Set() 为每个剩余元素 - 时间 n(最大)

对于 new Set() 操作，我猜它正在创建一个新对象并将每个元素添加到创建的实例中。

如果数据中有很多重复项，人们可能会期望提高效率。但是我们不希望数据中有很多重复项，并且根据我对“Big O”的理解，最大限制是所使用的。

根据此分析，我预计时间复杂度为 O(n^2) 或 O(n^3)。但如前所述，我不确定如何肯定地解释它。

如有任何帮助，我们将不胜感激。提前致谢!

Answer 1

我认为您对操作顺序的解释是正确的:过滤，然后映射，然后创建一个 Set。

但是，为了使该算法达到 O(n^2)，您必须创建一个嵌套循环，例如:

• 为数组的每个元素创建集合
• 将数组中的每个元素与其他元素进行比较。

这里不是这种情况。在最坏的情况下(没有重复)，算法将迭代输入数组三次，这意味着 O(3*n) 复杂度仍然是线性的，而不是二次的。