Time/Space 复杂性 - 如何计算出这个函数？
Time/Space Complexity - How to figure out in this function?
我需要计算这个问题的时间和 space 复杂度，谁能帮我弄清楚这是什么以及为什么？
我相信这个问题的时间复杂度是 O(n^2)，因为有 2 个过滤函数。从本质上讲，它类似于在数组上迭代的 2 个 for 循环，并且因为它们循环了一定的时间，我们知道第一个过滤器的 O(n) 并且添加另一个将使它成为 O (n^2)?
不确定 space 复杂度。
let arr = [1, 2, 2, 4, 4, 5, 6, 7, 7, 8, 9];
const result = arr.filter(x => arr.filter(y => y === x).length > 1)
console.log(result);
// 2, 2, 4, 4, 7, 7
我认为你对时间复杂度的看法是正确的，由于两个嵌套循环，它是 O(n^2)。
IMO space 复杂度为 O(n)，因为您只需要 n 个单位的 space 来保留数组，并且不会分配额外的内存。
是的，时间复杂度是 O(n^2) - 例如，如果 arr 有 10 个项目，算法需要进行 ~100 次比较才能完成。
Space 复杂度为 O(n)。例如，考虑外部 .filter 的最后一次迭代 - 几乎完成构建的 result 占用了 O(n) space （最坏情况；相当于输入端 arr)。正在过滤的回调内的内部数组（然后将对其 length 检查并返回）在最坏的情况下也将是输入 n 的一侧。因此，在任何时间点当前将被使用的最多 space 是 O(2n)，相当于 O(n).
我需要计算这个问题的时间和 space 复杂度，谁能帮我弄清楚这是什么以及为什么？
我相信这个问题的时间复杂度是 O(n^2)，因为有 2 个过滤函数。从本质上讲，它类似于在数组上迭代的 2 个 for 循环，并且因为它们循环了一定的时间，我们知道第一个过滤器的 O(n) 并且添加另一个将使它成为 O (n^2)?
不确定 space 复杂度。
let arr = [1, 2, 2, 4, 4, 5, 6, 7, 7, 8, 9];
const result = arr.filter(x => arr.filter(y => y === x).length > 1)
console.log(result);
// 2, 2, 4, 4, 7, 7
我认为你对时间复杂度的看法是正确的，由于两个嵌套循环，它是 O(n^2)。
IMO space 复杂度为 O(n)，因为您只需要 n 个单位的 space 来保留数组，并且不会分配额外的内存。
是的，时间复杂度是 O(n^2) - 例如，如果 arr 有 10 个项目，算法需要进行 ~100 次比较才能完成。
Space 复杂度为 O(n)。例如，考虑外部 .filter 的最后一次迭代 - 几乎完成构建的 result 占用了 O(n) space （最坏情况；相当于输入端 arr)。正在过滤的回调内的内部数组（然后将对其 length 检查并返回）在最坏的情况下也将是输入 n 的一侧。因此，在任何时间点当前将被使用的最多 space 是 O(2n)，相当于 O(n).