序列化到磁盤計數是否爲輔助空間複雜度？

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