空间复杂度是多少?我们如何获得它?(其中a和b是大小为N和M的数组)
a
b
N
M
a.filter(function(v) { return !b.includes(v); })
o4tp2gmn1#
空间复杂度是算法/函数/程序存储变量所需内存量的数学度量,就像时间复杂度是函数运行所需时间的度量。
O(n)
O(something)
例如,此函数:
function add(x,y) { return x+y; }
空间复杂度为O(1),因为它使用两个变量来存储数据:x和y。所以从技术上讲,你在内存空间中使用了 * 两 * 个"位置"。问题是,既然你使用了两个位置,为什么复杂度是O(1)?答案是,复杂度是用"规模"来表示的。这意味着,如果你的函数需要1,2,3,... 5个变量运行我们仍然在谈论"一"或常数.因此O(1)或"常数复杂度".另一个例子:
O(1)
x
y
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)的对数和(希望不是)"指数"空间复杂度的程序。阅读更多关于here、here和here的信息(这是关于时间复杂性的,但度量是相同的)
O(N)
O(N^2)
O(log N)
2^O(N)
1条答案
按热度按时间o4tp2gmn1#
空间复杂度是算法/函数/程序存储变量所需内存量的数学度量,就像时间复杂度是函数运行所需时间的度量。
O(n)
。O(something)
)。它是通过分析函数来发现的。通常是通过"长时间地盯着"代码来发现的例如,此函数:
空间复杂度为
O(1)
,因为它使用两个变量来存储数据:x
和y
。所以从技术上讲,你在内存空间中使用了 * 两 * 个"位置"。问题是,既然你使用了两个位置,为什么复杂度是O(1)
?答案是,复杂度是用"规模"来表示的。这意味着,如果你的函数需要1,2,3,... 5个变量运行我们仍然在谈论"一"或常数.因此O(1)
或"常数复杂度".另一个例子:
这个函数的空间复杂度是
O(N)
,为什么?因为我们使用了一个长度为3的数组,这个数组的长度可以是3,但是它也可以存储100000个值,因为我们在这里讨论的不仅仅是"1(或者,我们不能确定它只是几个值),计算机科学的家伙们决定我们将它表示为O(N)
或"线性复杂度"。例如,如果你的程序中需要一个2D数组,它可能具有
O(N^2)
或"二次复杂度",在某些情况下,你可能会遇到具有O(log N)
或2^O(N)
的对数和(希望不是)"指数"空间复杂度的程序。阅读更多关于here、here和here的信息(这是关于时间复杂性的,但度量是相同的)