时间/空间复杂性 - 如何弄清楚这个功能？

Question

我需要计算这个问题的时间和空间复杂度，任何人都可以帮我弄清楚它是什么以及为什么？

我相信这个问题的时间复杂度将是O（n ^ 2），因为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个单位的空间来保留数组，并且不会分配额外的内存。