此代码的 space 复杂度是多少

Question

代码的space复杂度是多少：

function double(n) {         //Here n is an array
   newArr = [];
   for (i = 0; i < n.length; i++) {
     newArr.push(2 * n[i]);
   }
  return newArr;
}

Answer 1

Since it has two variables newArr and i on which the space of this code depends.

不仅有两个变量名为newArr和i，还有n个变量名为newArr[0]、newArr[1]、newArr[2]，一直到newArr[n-1]。 Space 复杂性是指算法的存储量随输入数量增长的方式。由于您最多将 n 个元素推入 newArr，因此 space 复杂度为 O(n).

Answer 2

space 的复杂性确实是 O(N)，因为 space 不取决于您的程序定义了多少变量，而是取决于它最终会定义的 space 的最大数量在运行时占用。

将 space 复杂性视为程序在运行时产生的内存成本的因素。如果一个应用程序分配了它在程序运行期间所需的所有内存，在程序开始时并且这个数量与程序中的任何变量无关，那么该因素就是 1 即 space 的复杂性 O(1) - 一个常数，因为它不会改变。

这可能会令人困惑，因为您可能想知道为什么您的简单程序具有 space 的复杂性 O(N)，而随机的 C 应用程序在开始时分配 1GB 内存是只是 O(1)。这一切都归结为一个因素——如果 space 依赖于程序中的一个变量，那么 space 是该变量的一个因素，否则 space 是常数.

当有人说某个程序 O(1) space 复杂而另一个程序 O(N) 时，不要让它迷惑你，但也不要让它愚弄你； O(1) 并不总是意味着更少 space，O(N) 也不一定意味着更多 space。 Space 复杂性只是告诉您程序所需的 space 数量如何取决于程序本身的运行时执行。

此代码的 space 复杂度是多少

What is the space complexity of this code

data-structures

space-complexity