释放内存如何影响 space 复杂性？

Question

考虑以下伪代码：

linked_list_node = ... //We have some linked list
while linked_list_node is not NULL //Iterate through it 
    node_copy = CopyNode(linked_list_node) //We allocate a new pointer and copy the node, which is O(1) space
    ... //Do something
    DeleteAndFree(node_copy) //We free the memory allocated at the beginning of the loop
    Next(linked_list_node) //Advance once

让 N 成为我们链表的大小

一方面

在循环的每一次迭代中，我们使用了O(1)space次，循环是N次迭代，这意味着我们总共分配了 O(N) space

另一方面

我们实际上从来没有同时分配N个节点，每次我们恰好分配一个节点，所以理论上我们只需要O(1) Space。换句话说，如果我们的机器在内存中只有 1 个字节可用，它可以分配和删除相同的字节 一遍又一遍 ，永远不会运行进入内存限制。

我在堆栈溢出时发现了这个问题：

来自接受的答案：

However, if let's say for some reason the algorithm needs to allocate 'N' pointers when traversing a list of size N, ..., then the algorithm is considered to have a space complexity of O(N)

看来我的算法不满足这个条件，因为我实际上从来没有同时使用N个不同的指针，所以它应该是O( 1) Space。然而，它确实需要 N 分配操作，这可能就是为什么它真的是 O(N) Space

那么，space 的复杂性是多少？为什么？

Answer 1

这将是 O(1) 复杂度。在每一步，您都可以说您的使用量增加和减少 1，因此每个元素的净收益为 0。也就是说，这是一种奇怪的解决方案，因为您大概可以将其替换为分配单个节点并将每个元素复制到其中的实现。两者是等价的，后者显然是 O(1) space 的复杂度。

释放内存如何影响 space 复杂性？

How does freeing memory affect space complexity?

complexity-theory

space-complexity

一方面

另一方面