循环中声明的变量是否使 space 复杂度为 O(N)？

Question

在循环 N 次的 for 循环中声明的变量是否会使 space 复杂度为 O(N)，即使每次循环重复时这些变量都超出范围？

for(var i = 0; i < N; i++){
  var num = i + 5;
}

Answer 1

不，它仍然是 O(1)，如下所述：

for(var i = 0; i < N; i++){
  var num = i + 5; //allocate space for var `num`
} // release space acquired by `num`

Answer 2

Would variables declared inside an O(N) for loop make the space complexity O(N)

否，因为变量在每次迭代结束时超出范围，因此被销毁。

因此，space 复杂度保持不变，即 O(1)。

Answer 3

1 个（固定大小）变量，您更改 n 次（可能包括取消分配和重新分配）仍然只是 1 个变量，因此 O(1) space.

但这可能在某种程度上取决于语言 - 如果某种语言（或编译器）决定将所有这些早期的变量声明保留在内存中，那将是 O(n)，而不是 O(1).

例如，考虑在 C++ 中执行此操作的两种方法：

for (int i = 0; i < N; i++)
   int num = i + 5;

for (int i = 0; i < N; i++)
   int* num = new int(i + 5);

在前一种情况下，变量可以重复使用，它将是O(1)。

当您使用 new 时，该内存不会自动释放，因此后一种情况下的每次迭代都会分配更多内存，而不是重新使用旧内存（从技术上讲，指针会被重新使用，但它指向的内容to 将保留），因此它将使用 O(n) space。这样做是一个糟糕的主意，并且会导致内存泄漏，但这当然是可能的。

（我不太确定 C++ 标准对编译器在每种情况下需要做什么或不需要做什么，这主要是为了表明这种类型的循环内赋值不一定总是O(1)).

Do variables declared in loop make space complexity O(N)?