递归随机树结构的时间和space复杂度

Question

我试图找到一个很好的例子来理解递归映射随机树时的时间和 space 复杂性（大 O 表示法）。

我找到了二叉搜索树的示例，但我不确定这种情况是否适用于我的情况。

假设我们有一棵节点树。这些节点中的每一个也可以有随机数量的子节点。

ParentNode[ChildNode1.1[ChildNode2.1,ChildNode2.2], ChildNode1.2[ChildNode2.3]]

我的任务是将 ParentNode 复制到一个包含所有子节点的新 CopyNode 中。为此，我的职能是：

CopyNode = getChildNode(ParentNode)

Node getChildNode(Node node){
    Node newNode = node.copy();
    if (node.getChildren().empty()){
        return newNode
    }
    for (Node child: node.getChildren()){
        newNode.addChild(getChildNode(child))
    }
    return newNode;
}

如你所见，它是一个递归函数，迭代到树中的所有分支和节点。

我有两个问题。

函数的时间和 space 复杂度是多少。我不确定它是否是 O(n)，因为一些递归函数是这样工作的。或 O(XeN) 指数。
可能是实现该功能的有效方法吗？

Answer 1

node.copy() 每个源节点只调用一次。时间复杂度确实是 O(N)（N 是源树中的节点数）。

Space 复杂度与源代码树的深度成正比。最坏的情况又是 O(N).

没有必要对 node.getChildren().empty() 的特殊情况进行测试。

递归随机树结构的时间和space复杂度

Time and space complexity of recursive random tree structure

algorithm

recursion

time-complexity

big-o

space-complexity