math - 树遍历方法的大 O 表示法

Question

对于树结构中的每个节点（在前序遍历中）也必须触及所有祖先节点的方法的大 O 运行时复杂度是多少？O（n * avg（树高））？那就是我们的方法/函数的运行时复杂度是 O(n * avg(tree-height))？（在平均情况下）。

也许 avg(tree-height) 可以定义为 (min + max) / 2，但是 hm

Answer 1

我可能误解了，但如果你说你需要遍历所有节点（n），然后触摸每个节点的每个祖先（最坏的情况：在平衡二叉树中记录 n），那么我认为它会是O(n*Log(n)). 常数不适用于大 O 表示法，但（如下面的@interjay 所指出的）平均值可能适用。

假设一棵不平衡的树，你接触所有祖先的最坏情况大约是n/2，也就是大 O 中的 n。