我有一个简单的程序来序列化二叉树。代码:

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

最佳答案

这本质上是一个递归树遍历,因此它是 O(n)。请参阅以下内容以获得良好的概述:Big-Oh for Recursive Functions

关于space-complexity - 序列化到磁盘算作辅助空间复杂度吗?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/30623706/

10-11 22:32