javascript 中链接方法的复杂性

Question

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

例如，假设我们有一个函数，它 return 对一个数组求其正数的总和

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

因此，该函数的复杂性是多少？

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

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}

所以此刻我需要特别了解它的复杂性，因为我们正在处理 嵌套方法，例如在 map

中调用的过滤器

因此欢迎使用任何通用方法来确定此类算法的复杂性。

注意：这道题的所有复杂度都是时间复杂度而不是space

谢谢

Answer 1

链接方法实际上只是为了方便。 map() 或 filter() returns 一个数组。现在你可以先在数组上写一个名字，比如 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 Dabas 回答了你的问题；我在评论中回答你的问题：

So could you give me an example of what I can do to improve the code or some useful links

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

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 表示法只是描述了一些代码在输入数据增加时的行为方式。只有当你知道这是一个问题时才着眼于优化代码。

javascript 中链接方法的复杂性

Complexity of chaining methods in javascript

javascript

algorithm

complexity-theory

time-complexity