Краткий ответ:
Только то, что алгоритм имеет log (n) как часть своего анализа, не означает, что дерево вовлечено. Например, ниже приведен очень простой алгоритм, который O(log(n)
for(int i = 1; i < n; i = i * 2)
print "hello";
Как видите, дерево не было задействовано. Джон также приводит хороший пример того, как можно выполнить бинарный поиск в отсортированном массиве. Оба требуют O (log (n)) времени, и есть другие примеры кода, которые могут быть созданы или на которые есть ссылки. Так что не делайте предположений, основанных на асимптотической сложности времени, посмотрите на код, чтобы знать наверняка.
Подробнее о деревьях:
То, что алгоритм включает «деревья», также не означает O(logn)
. Вам нужно знать тип дерева и то, как операция влияет на дерево.
Некоторые примеры:
Вставка или поиск следующего несбалансированного дерева будет O(n)
.
Вставка или поиск следующих сбалансированных деревьев приведет к O(log(n))
.
Сбалансированное бинарное дерево:
Сбалансированное дерево степени 3:
Дополнительные комментарии
Если у деревьев, которые вы используете, нет способа «сбалансировать», то есть большая вероятность, что ваши операции будут O(n)
по времени, а не O(logn)
. Если вы используете деревья с самобалансировкой, то вставки обычно занимают больше времени, так как балансировка деревьев обычно происходит на этапе вставки.