javascript 空间复杂度js函数

iyfjxgzm  于 2023-01-19  发布在  Java
关注(0)|答案(1)|浏览(117)

空间复杂度是多少?我们如何获得它?(其中ab是大小为NM的数组)

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

o4tp2gmn1#

空间复杂度是算法/函数/程序存储变量所需内存量的数学度量,就像时间复杂度是函数运行所需时间的度量。

    • TL; DR**你不能用任何JS函数得到它。它是你必须"计算"的东西。在你的算法中,使用两个数组,空间复杂度将是O(n)
    • 说明**如果您想了解更多有关空间复杂度的信息:在计算机科学领域,空间复杂度使用"大噢"符号(O(something))。它是通过分析函数来发现的。通常是通过"长时间地盯着"代码来发现的

例如,此函数:

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

空间复杂度为O(1),因为它使用两个变量来存储数据:xy。所以从技术上讲,你在内存空间中使用了 * 两 * 个"位置"。问题是,既然你使用了两个位置,为什么复杂度是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的数组,这个数组的长度可以是3,但是它也可以存储100000个值,因为我们在这里讨论的不仅仅是"1(或者,我们不能确定它只是几个值),计算机科学的家伙们决定我们将它表示为O(N)或"线性复杂度"。
例如,如果你的程序中需要一个2D数组,它可能具有O(N^2)或"二次复杂度",在某些情况下,你可能会遇到具有O(log N)2^O(N)的对数和(希望不是)"指数"空间复杂度的程序。
阅读更多关于hereherehere的信息(这是关于时间复杂性的,但度量是相同的)

相关问题