遍历n-ary树的时间复杂度好像有多个正确答案，哪个最正确？
Time Complexity of traversing n-ary tree seems to have multiple correct answers, which is most correct?
忽略space复杂度，假设树中的每个节点恰好被触及一次，考虑DFS和BFS遍历时间等价，遍历一棵n-ary树的时间复杂度是多少？
鉴于大 O 表示法是一种渐近度量，这意味着我们正在寻找一个函数，当它扩展到更多级别或分支时，它会为我们提供最适合问题的直线或曲线。
我的直觉告诉我，对于一般的树结构，我们需要一个 b^l 类型的函数，其中 b 是分支因子，l 是树中的层数（对于完整且完整的树） .
但是对于部分树，取 b 和 l 的某种平均值是有意义的，也许是 AVG(b)^AVG(l)。
在寻找这个答案时，我发现很多人都说它是 O(n)，其中 n 是树中的顶点数（节点 -1）。看：
What is the time complexity of tree traversal? 和
但在我看来，线性解决方案并没有对算法在树添加额外级别（平均）时所花费的成本（及时）进行建模。这就是我所理解的大 O 符号的目的。
树的高度或分支因子不是完整遍历（无论是BFS还是DFS）复杂度的决定因素。只有顶点数才是决定因素。
如果你想用树的分支因子和高度来表达复杂性，那么你实际上是在问这些度量与树中节点数之间的关系。
正如您已经指出的那样，如果分支因子为 100，但一个节点很少有超过 3 个子节点，那么分支因子并不能真正告诉我们太多信息。关于树的高度也可以这样说。一棵高度为 4、分支因子为 2 的树可以有 5 到 31 个节点。
那怎么办？通常，会采用最坏的情况（最大化节点数）。这意味着您会将分支因子和高度转换为 完美 的树，即每个节点都有最大数量的子节点，树的叶子除外，它们都是同级别。
节点数则为ℎ+1-1，其中为分支因子，ℎ为高度（从根到叶的最长路径上的边数） .
这意味着给定和ℎ的最坏情况时间复杂度是O(ℎ+1)
使用 平均值 并不实用。分支因子的分布可能不是线性的，leaf-depths 的分布也可能不是线性的，因此使用平均值不会提供太多见解。
关于增加一个节点的代价：插入点确定后，增加一个节点的时间复杂度是恒定的。插入增加分支因子或增加树的高度都没有关系。
如果树是 搜索 树（如 BST 或 B-tree).在这种情况下，树的高度变得很重要，搜索的成本为 O(ℎ)。但是，如果树是 self-balancing（如 AVL 或 B-tree），则这种变化是有限的，并且这种复杂性将为 O(log)
忽略space复杂度，假设树中的每个节点恰好被触及一次，考虑DFS和BFS遍历时间等价，遍历一棵n-ary树的时间复杂度是多少？
鉴于大 O 表示法是一种渐近度量，这意味着我们正在寻找一个函数，当它扩展到更多级别或分支时，它会为我们提供最适合问题的直线或曲线。
我的直觉告诉我，对于一般的树结构，我们需要一个 b^l 类型的函数，其中 b 是分支因子，l 是树中的层数（对于完整且完整的树） .
但是对于部分树，取 b 和 l 的某种平均值是有意义的，也许是 AVG(b)^AVG(l)。
在寻找这个答案时，我发现很多人都说它是 O(n)，其中 n 是树中的顶点数（节点 -1）。看：
What is the time complexity of tree traversal? 和
但在我看来，线性解决方案并没有对算法在树添加额外级别（平均）时所花费的成本（及时）进行建模。这就是我所理解的大 O 符号的目的。
树的高度或分支因子不是完整遍历（无论是BFS还是DFS）复杂度的决定因素。只有顶点数才是决定因素。
如果你想用树的分支因子和高度来表达复杂性，那么你实际上是在问这些度量与树中节点数之间的关系。
正如您已经指出的那样，如果分支因子为 100，但一个节点很少有超过 3 个子节点，那么分支因子并不能真正告诉我们太多信息。关于树的高度也可以这样说。一棵高度为 4、分支因子为 2 的树可以有 5 到 31 个节点。
那怎么办？通常，会采用最坏的情况（最大化节点数）。这意味着您会将分支因子和高度转换为 完美 的树，即每个节点都有最大数量的子节点，树的叶子除外，它们都是同级别。
节点数则为ℎ+1-1，其中为分支因子，ℎ为高度（从根到叶的最长路径上的边数） .
这意味着给定和ℎ的最坏情况时间复杂度是O(ℎ+1)
使用 平均值 并不实用。分支因子的分布可能不是线性的，leaf-depths 的分布也可能不是线性的，因此使用平均值不会提供太多见解。
关于增加一个节点的代价：插入点确定后，增加一个节点的时间复杂度是恒定的。插入增加分支因子或增加树的高度都没有关系。
如果树是 搜索 树（如 BST 或 B-tree).在这种情况下，树的高度变得很重要，搜索的成本为 O(ℎ)。但是，如果树是 self-balancing（如 AVL 或 B-tree），则这种变化是有限的，并且这种复杂性将为 O(log)