这是 Space 复杂性的奇怪问题。有人可以提供任何见解吗？

Question

我在解决这个问题时点击了这个方法 -

给定一个单链表和一个整数 x。您的任务是完成 deleteAllOccurances() 函数，该函数删除链表中出现的所有键 x。该函数有两个参数：链表的头部和一个整数 x。该函数应该return修改链表的头部。

我不确定我的代码的 space 复杂度是多少。

我想因为我只使用了 1 个额外的节点 space 并且同时创建新节点和删除旧节点，所以它应该是 O(1)。

Node* deleteAllOccurances(Node *head,int x)
{
   Node *new_head = new Node(-1);
   Node *tail = new_head;
   Node *temp = head;
   Node *q;

   while(temp != NULL) {
      if(temp->data != x) {
        tail->next = new Node(temp->data);
        tail = tail->next;
      }

       q = temp;
       delete q;
       temp = temp->next;
    }

   tail->next = NULL;
   return new_head->next;
}

Answer 1

是的，因为您在任何时候分配了多少 space 并不取决于参数（例如列表的长度或列表中有多少 x 的值) space 函数的复杂度是 O(1)

space 复杂度的实际意义在于查看您的算法需要多少内存。您永远不需要超过 1 个内存节点（加上局部变量），O(1) 反映了这一点。

Answer 2

嗯，有点。

这取决于您是否将总分配视为净变化（在这种情况下您是对的）。

但是如果您正在考虑为新分配访问堆的次数，那么它会使用更多 space 和大量计算。（给定的 C++ 编译器和运行时不是有义务保证立即重用 space 在堆中释放，只是它可用用于重用.)

作为一名几十年的 C++ 程序员，您所做的事情有点令人恐惧，因为您正在做很多的新分配。这会导致堆分配结构的颠簸。

此外，您执行此操作的方式是将不匹配的内容推送到列表的末尾，因此您正在将内容打乱。

提示 - 您不需要创建任何个新节点。

Answer 3

衡量复杂性部分取决于您认为的变量。就列表中的节点数而言，您的算法在 space 用法中是 O(1)。但是，这可能不是这种情况下的最佳视角。

这种情况下的另一个变量是节点的大小。通常这个方面被复杂性分析所忽略，但我认为它在这种情况下是有价值的。虽然您的算法的 space 要求不取决于节点数，但它确实取决于节点的大小。节点中的数据越多，您需要的 space 就越多。令s为单个节点的大小；公平地说，您的算法的大小要求是 O(s).

此任务的更常见算法的大小要求是 O(1)，即使考虑到节点数和每个节点的大小也是如此。（它不需要创建任何节点，不需要复制数据。）我不会推荐你的算法。

为了避免全盘否定，我会将您的方法视为对传统方法的两个独立更改。一个变化是引入了虚拟节点 new_head。此更改很有用（事实上正在使用），即使您的实现会泄漏内存。它只比不使用虚拟头稍微低一些效率，并且它简化了从列表前面删除节点的逻辑。只要您的节点大小不过大，这就很好。

另一个变化是切换到复制节点而不是移动它们。这是一个令人畏惧的变化，因为它无偿地增加了程序员、编译器和执行的工作量。渐近分析（big-O）可能不会接受这个加法，但它没有任何有益的收获。您已经破坏了链表的一个关键优势，并且在 return.

中一无所获

让我们看看删除第二个更改。您需要添加一行，特别是将 new_head->next 初始化为 head，但这通过消除在末尾将 tail->next 设置为 nullptr 的需要来平衡。另一个添加是 else 子句，因此当前每次迭代运行的行不一定是每次迭代运行。除此之外，还有代码删除和一些名称更改：删除 temp 指针（改为使用 tail->next）并删除循环中新节点的创建。总而言之，与您的代码相比，这些更改严格减少了完成的工作（和内存需求）。

为了解决内存泄漏问题，我使用了本地虚拟节点而不是动态分配它。这删除了最后一次使用 new，这反过来又删除了问题评论中提出的大部分反对意见。

Node* deleteAllOccurances(Node *head, int x)
{
    Node new_head{-1};              //<-- Avoid dynamic allocation
    new_head.next = head;           //<-- added line
    Node *tail = &new_head;

    while(tail->next != nullptr) {
        if(tail->next->data != x) {
            tail = tail->next;
        }
        else {                      //<-- make the rest of the loop conditional
            Node *q = tail->next;
            tail->next = tail->next->next;
            delete q;
        }
    }

   return new_head.next;
}

此版本删除了 "cringe factor"，因为有利于创建一个节点，并且 new 未被使用。这个版本足够干净，无需每个人询问就可以进行复杂性分析 "why???".

这是 Space 复杂性的奇怪问题。有人可以提供任何见解吗？

This is strange question of Space Complexity. Can someone provide any insights?

c++

linked-list

space-complexity