空间复杂度js函数

Question

什么是空间复杂度以及我们如何获得它？（其中a和b是大小为N和的数字数组M）

a.filter(function(v) {
   return !b.includes(v);
})

Answer 1

空间复杂度是算法/函数/程序存储其变量所需的内存量的数学度量。就像时间复杂度衡量您的函数需要运行多少时间一样。

快速回答您的问题：您无法通过任何 JS 函数获取它。这是你必须“计算”的东西。在您的算法中，使用两个数组，空间复杂度为O(n)。

如果您想更多地了解空间复杂度：在计算机科学世界中，空间复杂度使用“大哦”符号 ( O(something))。这是你通过分析你的函数发现的东西。通常通过“长时间凝视”您的代码

例如这个函数：

function add(x,y) { return x+y; }

具有 的空间复杂度O(1)。因为它使用两个变量来存储其数据：x和y。因此，从技术上讲，您在内存空间中使用了两个“位置”。问题是，既然你用了两个地方，为什么复杂度是O(1)？答案是，复杂性以“规模”表示。这意味着，如果您的函数需要 1、2、3、... 5 个变量来运行，我们仍然在谈论“一个”或常量。因此O(1)或“恒定的复杂性”。

另一个例子 ：

function sum(arr, n) {
  var sum = 0;
  for(var i=0; i<n; i++) {
    sum += arr[i];
  }
}

在这种情况下，这个函数的空间复杂度是O(N)Why？因为我们使用的是一定长度的数组。这个数组的长度可以是 3，但它也可以存储 100 000 个值。由于我们在这里不只是谈论“一个”（或者，我们不能确定它只是几个值），因此计算机科学人员决定我们将其表示为O(N)“线性复杂性”。

等等等等。例如，如果您的程序中需要一个二维数组，它可能具有O(N^2)“二次复杂度”。在某些情况下，你能碰到与对数和（希望不是）“指数”空间的复杂程序O(log N)或2^O(N)。

在此处、此处和此处阅读有关它的更多信息（这是关于时间复杂度的，但度量是相同的）