JavaScript中链接方法的复杂性

Question

我在确定算法的复杂性方面遇到了问题，因为它使用了ES6 的特性，当然它们是链式方法。我已经知道这些方法的一些基本复杂性，例如Array.prototype.map的复杂性是O(n(。但是当我们想要确定算法的复杂性时，我们如何管理链式方法？

例如，假设我们有一个函数，它为数组返回其正数的总和

let sumPositive = arr => arr.filter(i => i > 0).reduce((a, b) => a + b, 0);
console.log(sumPositive([1, 2, 3, -4])); // 6
console.log(sumPositive([1, 2, 3, 4])); // 10

因此，该功能的复杂性是什么？

另一个例子是这个算法，对于给定的字符串，返回字符串中每个字符的计数

let charCount = str =>  str.split('').map(
(c,_,str) => str.filter(i => i===c)
).reduce((a, b) => a.hasOwnProperty(b[0]) ? a : ({...a, [b[0]]: b.length}), {});
console.log(charCount("hi")); // {"h": 1, "i": 1}
console.log(charCount("hello to you")); // {"h": 1, "e": 1, "l": 2, "o": 3, " ": 2, "t": 1, "y": 1, "u": 1}

所以在这一秒，我需要特别了解它的复杂性，因为我们正在处理嵌套方法，例如在映射中调用的过滤器

因此，任何确定此类算法复杂性的通用方法都是受欢迎的。

注意：本题中的所有复杂度都是时间复杂度而不是空间

谢谢

Answer 1

链接方法实际上只是为了方便。map()或filter()返回一个数组。现在你可以先在数组上放一个名字，比如let result = arr.map(...)，然后在那个result数组上做其他事情，或者你可以直接对map()(或filter()(返回的数组做一些事情，比如map().filter().<more chaining if you want>。

因此，它等效于顺序执行。考虑这个例子，

let sumPositive = arr => arr.filter(i => i > 0)
.reduce((a, b) => a + b, 0);
let arr = [1, 2, 3, -4];
let filteredArray = arr.filter(i => i > 0); // O(n)
let reducedResult = filteredArray.reduce((a, b) => a + b, 0); // O(n)
console.log(sumPositive(arr)); // 6
console.log(reducedResult) // 6

现在你看到filter()需要O(n)然后reduce()需要O(n)，所以你得到O(n) + O(n) ==> O(n)作为你的最终时间复杂度。

我希望你能同样地发现第二个例子的复杂性。如果您需要帮助，请在评论中告诉我。

Answer 2

@Ajay达巴斯回答了你的问题;我在评论中回答您的问题：

所以你能给我一个例子，说明我可以做些什么来改进代码或一些有用的链接

你的第一个例子不会变得更简单，但你可以降低第二个算法的时间复杂度：

let charCount = str =>  str.split('')
.map((c,_,str) => str.filter(i => i===c))
.reduce((a, b) => a.hasOwnProperty(b[0]) ? a : ({...a, [b[0]]: b.length}), {});

您可以通过不使用filter()方法来执行此操作。如果您维护所有键及其当前计数的索引，则无需执行此操作。你已经在用reduce()这样做了：

let charCount = str => 
return str.split('').reduce(
(acc, nextChar) => {
return {
...acc,
[nextChar]: (acc[nextChar] || 0) + 1
};
},
Object.create(null)
);
};

这应该是O(n)- 我们只迭代数组两次。请注意，我们不需要filter()结果，因为我们需要做的就是在累加器中获取该字符的现有计数并将其递增 1。

Object.create(null)的用途是创建一个具有null原型的新对象 - 这意味着我们不需要使用hasOwnProperty().

您应该记住，仅仅因为某些内容O(n^2)并不意味着存在性能问题。大 O 表示法只是描述了随着输入数据的增加，某些代码的行为方式。只有在知道代码有问题时才考虑优化代码。