Space 在 ArrayList 或 Map 中添加树/图的 n 个节点的复杂度

Question

假设我们有一个二叉树

class node {
   int data;
   node left;
   node right;
}

现在假设我创建了一个 ArrayList<node> 并在其中添加了所有 n 个节点，它的复杂度是常量 space 还是 n？

我的困惑是，由于 node 不是原始数据结构而是对象，它必须使用 CALL BY REFERENCE，因此它不应该使用额外的 space 来更改某些数据在节点的 class 实例中，也在 ArrayList<> 中进行更改。

此外，我推测 ArrayList<type> abc = xyz; //another arraylist of same type 使用 CALL BY REFERENCE 因此它使用常量 space，但是 ArrayList<type> abc = new ArrayList<>(xyz) 创建了一个新实例因此它应该使用额外的 space.

现在，当我在 ArrayList<node> 中添加 class 个实例时，我必须使用 new 关键字初始化数组列表， ArrayList<node> abc = new ArrayList<>(); 在我将实例添加到列表。所以它应该使用额外的 space 但是因为我们正在使用已经在树中定义的 class 实例并且树中的任何更改也会反映在列表中，因此它应该使用常量 space。以上哪一个是正确的，我哪里错了？

EDIT ：我知道即使是引用也会占用一些space，但不会比实际占用的内存少很多吗space最初的对象？

Answer 1

node is not a primitive data structure but an object

Java 中没有对象 variables/fields。只有原始变量和参考变量。

it must use CALL BY REFERENCE

Java 仅按值调用。基元按值传递，引用按值传递。

when I am adding class instances in ArrayList

Java 不支持此功能。您只能添加引用。

So it should use extra space

只有添加的引用使用额外的 space。对象未被复制。

Answer 2

space 复杂度当然是 n 的函数，而不是常数。这是因为即使 ArrayList 只包含对树对象的引用，这些引用本身也会占用 space（我不是 JVM 专家所以我不确定确切的数量，但它只是几个字节） .当然引用占用的space会比对象本身占用的少很多，但还是会占用space.

编辑:

明确地说，如果您问的是 ArrayList 占用的空间是否 space 少于对象本身，那么是的，确实如此，但那是 而不是 space 复杂性意味着什么。 Space 复杂性与存储数据需要多少 space 无关，而是关于 space 要求如何随着数据的增长乘以。当我说 space 复杂度是 O(n) 或线性时，我的意思是 ArrayList 大小按比例增加与对象的数量。对象数量的两倍使 ArrayList 的大小增加一倍，对象数量的五倍使 ArrayList 的大小增加五倍，依此类推。常数或 O(1) 复杂度意味着，即使您可能需要额外的 space，space 的数量你需要保持不变，不会随着你添加项目而增加。

我相信你真正想问的是 "Will adding an ArrayList double my space requirements, or will it require no extra space?" 而我对两者的回答是否定的。它不会加倍 space 要求，因为它只使用引用，但它需要一些额外的 space 来存储这些引用。这与 space 复杂性无关。

TLDR: Space 要求 ≠ Space 复杂性.

Space 在 ArrayList 或 Map 中添加树/图的 n 个节点的复杂度

Space complexity of adding n nodes of a tree / graph in an ArrayList or Map

java

oop

arraylist

space-complexity