时间/空间复杂性-如何在此函数中计算？

Question

我需要计算这个问题的时间和空间复杂度，有人能帮我弄清楚这是什么吗?为什么？

我相信这个问题的时间复杂度是O(n^2)，因为有2个过滤函数。本质上，这类似于有两个for循环在数组上迭代，因为它们循环了一段时间，我们知道第一个过滤器将是O(n)，添加另一个过滤器将使其为O(n^2)？

不确定空间的复杂性。

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

Answer 1

是的，时间复杂度是O(n^2)的-例如，如果arr有10个项目，算法需要进行大约100次比较才能完成。

空间复杂度是O(n)。例如，考虑外部.filter的最后一次迭代-即将完成构造的result此时占用了O(n)空间(最坏的情况；相当于输入arr的一侧)。被过滤的回调中的内部数组(然后检查并返回它的length )也将是最坏的情况，即输入n的一端。因此，当前在任何时间点使用的最大空间是O(2n)，它相当于O(n)。

Answer 2

我认为你对时间复杂度的估计是正确的，由于两个嵌套循环，它是O(n^2)。

IMO空间复杂度为O(n)，因为您只需要n个单位的空间来保存数组，并且没有分配额外的内存。