Биг-О нотация и рекурсия с петлями

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

В худшем случае вам всегда придется пересекать все элементы.Вы можете представить, что в реальных приложениях, когда N-арное дерево будет использоваться в качестве структуры данных для файловой системы.Каждый узел - это файл (каталог или обычный файл), и вы хотите найти файл по имени, который находится в правом нижнем углу дерева, вы не можете сделать это, не проверив все узлы, поэтому странно хранить некоторую дополнительную информацию, чтобы направить васчтобы файл быстрее (это, например, то, что команда find под linux будет делать при поиске файла по имени).

Answer 2

Если n-арное дерево не имеет структуры (ключи дочерних элементов / узлов не имеют сортировки на основе сравнения), то худшим случаем будет O (N).

Если n-арное дерево не обязательно сбалансировано (то есть каждый узел может иметь одного ребенка в наихудшем случае), то наихудшим случаем также будет O (N).

Если дерево является сбалансированным и отсортированным n-арным деревом O (log ₂ (n) log _n (N)) Где:

• N = # узлов в дереве
• n = # число детей в каждом узле

Пояснение:

Двоичный поиск по n дочерним элементам займет O (log ₂ (n)) по глубине дерева, что является максимальным значением O (log _n (N)) в сбалансированное n-арное дерево.

Answer 3

Процитируем вас в конце там:

... наихудший случай, когда нам нужно пройти через каждого потомка дерева .

Если вы просматриваете каждого потомка в худшем случае, это будет O(n), где n - это количество узлов в дереве.

Вы можете думать об этом следующим образом: если бы это был простой связанный список, и вам пришлось бы искать его полностью в худшем случае, какой была бы сложность в худшем случае?Здесь то же самое.Просто в этом случае каждый узел может иметь более одного дочернего элемента.

И рекурсия на самом деле здесь не играет роли в изменении сложности.Это просто средство для зацикливания.Это было бы то же самое, если бы вы выполняли итеративный поиск с использованием стандартной конструкции цикла.