链接列表的空间复杂性

Question

我的问题是，如果我们对Java或Python中的对象创建多个参考变量，那么空间复杂性会增加还是相同？

例如，我有一个链接的输入大小n的链接列表，该列表是头 如果我创建另一个参考变量重复，并将其指向头部，就像

public LinkedList duplicate(LinkedList head)
{    
LinkedList duplicate=head;
return duplicate;
}

在这种情况下是o（1）或o（n）的其他空间复杂性是什么？

Answer 1

空间复杂性保持线性或O（n）

Answer 2

是的，是o（n）。新对象是在堆空间中创建的，并且对这些对象的引用存储在堆栈内存中。

Answer 3

我相信应该是o（1）空间复杂性。我们通常不会考虑空间复杂性中输入参数的大小，因为您实际上无能为力地改进或消除它们。我们只关心我们在算法中创建额外的缓冲区。考虑阵列相同。

1. 没有其他缓冲区。空间复杂性：O（1）

public int[] noBufferMethod(int[] data) {
    int[] justReference = data; // Points to input so no extra space
    return justReference;
}

2. 带有其他缓冲区。空间复杂性：O（n）

public int[] withBufferMethod(int[] data) {
    int[] buffer = new int[data.length]; // Creates additional buffer
    return buffer;
}

完全相同的LinkedList（或任何集合）。

Answer 4

您要求其他空间复杂性，对吗？

在您的情况下，附加空间复杂性仍然是恒定的，只是创建一个参考变量并将其指向头部，不会再次创建整个链接列表，它只是指向头节点的另一个变量，并且没有创建任何额外的节点。任何新节点都是使用java中的new关键字创建的。

总空间复杂性仍然是O（n），因为它是您的linkedlist占用的空间。