Будет ли сериализация на диск считаться дополнительной сложностью пространства?

Question

У меня есть простая программа для сериализации двоичного дерева. Код:

public static <T> void serialize(TBST<T> tree, String fileName) throws FileNotFoundException, IOException { 
     /* 
     * using only 1 file will create a lot of confusion in coding. 
     */ 
     try (ObjectOutputStream oosNodeData = new ObjectOutputStream(new FileOutputStream(fileName))) { 
       preOrderSerialization(tree.getRoot(), oosNodeData); 
     } 
    } 


    private static <T> void preOrderSerialization(TBSTNode<T> node, ObjectOutputStream oosNodeData) throws IOException { 
     if (node == null) { 
      return;         
     } 

     oosNodeData.writeObject(node.element); 

     preOrderSerialization(node.left, oosNodeData); 
     preOrderSerialization(node.right, oosNodeData); 
    } 

Как мы видим, сама программа не использует дополнительное пространство. Однако он делает то, что сказал - сериализует. Какова сложность пространства? O (n) или O (1)? please ignore the stack space

Answer 1

Это, по сути, рекурсивный обход дерева и, как таковой, это будет O (n). Для хорошего обзора см. Следующее: Big-Oh for Recursive Functions