Big-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个孩子。最好的情况是elem等于root.data。

但是我不确定在最坏的情况下我们必须经历树上的每个孩子。

Answer 1

在最后引用您：

...最坏的情况下，我们必须穿过树上的每个孩子。

如果在最坏的情况下遍历每个孩子，那将是O(n)，这n是树中节点的数量。

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

递归在改变复杂性方面实际上并不起作用。这只是循环的手段。如果您使用标准循环结构进行迭代搜索，那将是相同的。