javascript - 空间复杂度 js 函数

Question

什么是空间复杂度，我们如何获得它？ (其中 a 和 b 是大小为 N 和 M 的数组)

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

Answer 1

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

TL;DR 您无法通过任何 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)为什么？因为我们使用的是一定长度的数组。这个数组的长度可以是 3，但它也可以存储 100 000 个值。由于我们在这里谈论的不仅仅是“一个”(或者，我们不能确定它只是几个值)，计算机科学人员决定我们将其表示为 O(N)或“线性复杂度”。

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

阅读更多相关信息 here , here和 here (这是关于时间复杂度，但措施是相同的)