java - 大 O 符号和带循环的递归

Question

以下方法中最坏情况的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; 
}

这是一棵 n 元通用树，每棵树都有 n 个 child 。最好的情况发生在 elem 等于 root.data 时。

但我不确定我们必须遍历树的每个 child 的最坏情况。

Answer 1

在最后引用你的话:

... the worst case where we have to go through every child of the tree.

如果您在最坏的情况下遍历每个 child ，那将是 O(n)，其中 n 是树中的节点数。

您可以这样想:如果这是一个简单的链表，并且您必须在最坏的情况下完全搜索它，那么最坏情况的复杂度是多少？这里也一样。只是在这种情况下，每个节点可以有多个子节点。

并且递归在改变复杂性方面并没有真正发挥作用。这只是循环的手段。如果您使用标准循环结构进行迭代搜索，结果会是一样的。