求泛型n叉树contains方法最坏情况的Big-O时间复杂度

让我来拆解这个方法的逻辑，帮你确定它的最坏情况Big-O表示法：

首先先贴出你给出的实现代码：

/**
 * @best-case O(1)
 * @worst-case O(?)
 *
 * {@link NTree#contains(Comparable)}
 */
public boolean contains(T elem) {
 if (this.data.compareTo(elem) == 0)
 return true;
 for(NTree<T> t : children) {
 if(t != null)
 return t.contains(elem);
 }
 return false;
}

先理清方法的遍历逻辑 #

这个方法是**深度优先遍历（DFS）**的变种：先检查当前节点是否匹配目标元素，如果不匹配，就依次遍历子节点——注意这里只要遇到第一个非空子节点，就立刻递归进去，不会继续遍历其他兄弟节点，直到递归返回结果。

最坏情况的场景 #

最坏情况包含两种情况：

• 目标元素不存在于树中：这时候方法必须遍历每一个节点，确认所有节点都不匹配，最后才返回false。
• 目标元素存在，但位于树的最深处的最后一个分支节点：这时候方法会先遍历完前面所有分支的节点，最后才找到目标元素。

时间复杂度推导 #

不管树是满n叉树、不平衡的n叉树，最坏情况下我们都需要访问所有N个节点（N是树的总节点数），每个节点只被访问一次，对应的时间复杂度就是O(N)。

这里不用树的高度h来描述，是因为满n叉树的节点数N和高度h的关系是N = (n^(h+1)-1)/(n-1)，但直接用节点总数N来描述最坏情况的复杂度更直观——毕竟我们的操作次数和节点总数是线性相关的。

内容的提问来源于stack exchange，提问作者Filipe Nóbrega