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

Question

单击此方法时我正在解决此问题-

给出单个链表和一个整数x。您的任务是完成函数deleteAllOccurances（），该函数删除链表中出现的所有出现的键x。该函数有两个参数：链接列表的头部和整数x。该函数应返回修改后的链表的头部。

我不确定代码的空间复杂度是什么。

我想因为我仅使用1个额外的Node空间，并且同时创建了新节点并删除了旧节点，所以应该为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

嗯，有点。

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

但是如果您正在考虑为新分配而击中堆的次数，那么它将占用更多的空间和大量的计算。 （给定的C ++编译器和运行时not必须保证立即重用堆中释放的空间，只是要available进行重用。）

作为C ++程序员数十年，您正在做的事情令人有些恐惧，因为您正在做lot新分配。这会导致堆分配结构的崩溃。

此外，您执行此操作的方式是将与列表末尾不匹配的内容推送到列表中，因此您将内容拖曳了下来。

提示-您不需要创建any新节点。

Answer 2

是的，因为您一次分配的空间不取决于参数（例如，列表的长度或列表中x的值多少，所以该函数的空间复杂度为[ C0]

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

Answer 3

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

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

即使同时考虑节点数和每个节点的大小，对此任务更通用的算法的大小要求为O(s)。 （它不需要创建任何节点，也不需要复制数据。）我不建议您在该节点上使用您的算法。

---

为了避免全部消极，我认为您的方法是对传统方法的两项独立更改。一种更改是引入了虚拟节点O(1)。即使您的实现会泄漏内存，此更改也是有用的（实际上正在使用中）。它的效率仅比不使用虚拟磁头低一点，并且简化了从列表开头删除节点的逻辑。只要您的节点大小不太大，这就很好。

另一个变化是切换到复制节点而不是移动它们。这是值得大刀阔斧的变化，因为它无意中增加了程序员，编译器和执行的工作。渐近分析（big-O）可能不会对此增加，但是它没有任何有益的收益。您已经浪费了链接列表的主要好处，却一无所获。

让我们看看删除第二个更改。您将需要添加一行，特别是将new_head初始化为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;
}

。此版本非常干净，可以进行复杂性分析，而无需每个人都问“为什么？”。]