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

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）空间，该循环是N个迭代，这意味着我们总共分配了[[O（N）空间]

另一方面

我们从未实际分配

N个节点，每次我们只分配一个节点时，因此，理论上，我们只分配O（1）Space

。换句话说，如果我们的机器在内存中只有1个字节可用，则它可以分配和删除同一字节一遍又一遍，而永远不会遇到内存限制。

---

我在堆栈溢出时发现了这个问题：What is O(1) space complexity?

来自接受的答案：

但是，如果由于某种原因，该算法在遍历大小为N，...的列表时需要分配'N'指针，则该算法被认为具有O（N）的空间复杂度

似乎我的算法不满足此条件，因为我从未实际使用

N个不同的指针同时

，因此应为O（1）Space。但是，它确实需要N分配操作，这可能就是为什么它实际上是O（N）Space的原因那么，它的空间复杂度是什么，为什么？

Answer 1