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()TakesO(n)和reduce()Takes O(n)，因此您将得到O(n) + O(n) ==> O(n)最终的时间复杂度。

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