相同DOM树查找对应节点的两种实现的平均及最坏时间复杂度是多少？

问题1：迭代解法的时间复杂度 #

• 你考虑indexOf的开销是对的，但它不会把最坏复杂度拉高到超过O(n)。因为整棵DOM树的所有子元素集合的总长度就是n-1（所有非根节点都属于某个父节点的children列表），你路径上所有indexOf的总遍历次数加起来最多就是n-1，加上路径本身的长度开销，最坏复杂度依然是O(n)，符合你之前的判断。
• 关于平均复杂度：如果是完全平衡树这类结构，每一层的父节点的子节点数量都是常数（比如二叉树就是2），那每一层indexOf的开销就是O(1)，路径长度是O(logN)，平均时间复杂度确实是O(logN)。
• 你提到的叶子节点indexOf开销到O(n)的极端场景，只存在于星型结构的树（根节点直接挂所有其他节点），这种场景下路径长度只有1，总开销依然是O(n)，属于最坏复杂度的覆盖范围，不会额外拉高复杂度上限。

问题2：递归DFS实现的复杂度对比 #

• 这个递归实现的最坏复杂度依然是O(n)，比如目标节点是前序遍历顺序的最后一个节点，你需要遍历整棵树的所有节点才能找到。但它的平均复杂度不是O(logN)，比迭代解法要高：
  这个DFS是前序遍历，只要目标节点不是当前路径上的第一个节点，你就需要遍历完它所有前面的兄弟节点的整棵子树，比如目标节点是根节点的第二个子节点的后代，你就得先把第一个子节点的所有后代全部遍历一遍才能进入第二个子节点的分支，这部分无关节点的遍历开销是完全多余的。
• 关于是否比迭代优：绝大多数场景下迭代实现的表现更好。
  首先DOM节点的子节点数量通常都很少，indexOf的开销可以忽略不计，而迭代不会遍历任何无关的子树，开销完全和目标节点的深度挂钩，表现非常稳定。反而递归在目标节点遍历顺序靠后时，会产生大量多余的遍历开销，甚至远高于indexOf的成本。
• 补充注意点：这个递归实现没有写默认返回值，如果目标节点不存在会返回undefined，生产环境用的话可以补个兜底返回。

内容的提问来源于stack exchange，提问作者Joji