我有一个简单的程序来序列化二叉树。代码:
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/