O (logn) всегда дерево?

Question

Мы всегда видим операции на (бинарном поиске) дереве, которое имеет самое наихудшее время работы O (logn) из -за высоты дерева. Интересно, говорят ли нам, что алгоритм имеет время работы в зависимости от функции logn, например, m + nlogn, можем ли мы сделать вывод, что он должен включать (дополненное) дерево?

РЕДАКТИРОВАТЬ: Благодаря вашим комментариям, теперь я понимаю, что Divide-Conquer и Binary Tree настолько похожи визуально/концептуально. Я никогда не устанавливал связь между ними. Но я думаю о случае, когда O (logn) не является алгоистом, который включает в себя дерево, которое не имеет свойства BST/AVL/Red-Black Tree.

Это непересекающаяся набор структуры данных с операциями Find/Union, время работы которого составляет O (N + MLOGN), причем N является # элементов и M - количество операций находки.

Пожалуйста, дайте мне знать, если я пропускаю STH, но я не вижу, как здесь вступает в игру. Я просто вижу в этом (Discoint Set) случай, что в нем есть дерево без свойства BST, и время выполнения функции LOGN. Так что мой вопрос о том, почему/почему я не могу сделать обобщение из этого дела.

Answer 1

То, что у вас есть, точно назад. O(lg N) Обычно означает какой -то алгоритм разделения и завоевания, а один общий способ реализации разделения и завоевания - это двоичное дерево. В то время как бинарные деревья являются существенным подмножеством всех алгоритмов разделения и подтверждения, в любом случае являются подмножеством.

В некоторых случаях вы можете преобразовать другие алгоритмы разделения и завоевать довольно непосредственно в двоичные деревья (например, комментарии на другом ответе уже предприняли попытку претендовать на бинарный поиск аналогичным). Однако, для другого очевидного примера, многолетнего дерева (например, B-три, B+ дерево или дерево B), в то время как ясно, что дерево так же ясно нет двоичное дерево.

Опять же, если вы хотите достаточно сильно, вы можете растянуть точку, что многолетнее дерево может быть представлено как своего рода искаженная версия бинарного дерева. Если вы хотите, вы, вероятно, можете растянуть все исключения до такой степени, что все они (по крайней мере, что -то вроде) бинарных деревьев. По крайней мере, для меня, однако, все, что делает, это делает «бинарное дерево» синонимом «Разделение и завоевание». Другими словами, все, что вы достигаете, - это искажение словарного запаса и, по сути, уничтожать термин, который является одновременно отличным и полезным.

Answer 2

Нет, вы также можете бинарный поиск сортированного массива (например). Но не верьте мне на слово http://en.wikipedia.org/wiki/binary_search_algorithm

Answer 3

В качестве счетчика:

given array 'a' with length 'n'
y = 0
for x = 0 to log(length(a))
    y = y + 1
return y

Время выполнения o (log (n)), но здесь нет дерева!

Answer 4

Ответ нет. Бинарный поиск отсортированного массива O(log(n)).

Answer 5

Алгоритмы, принимающие логарифмическое время обычно найдено в операциях на бинарных деревьях.

Примеры O (logn):

• Поиск предмета в отсортированном массиве с бинарным поиском или сбалансированным деревом поиска.

• Посмотрите значение в отсортированном массиве ввода по делу.

Answer 6

Поскольку o (log (n)) является лишь верхней границей также все алгоритмы O (1) function (a, b) return a+b; удовлетворить состояние.

Но я должен согласиться со всеми алгоритмами Theta (log (n)) вроде как алгоритмы деревьев или, по крайней мере, могут быть абстрагированы на дерево.

Answer 7

Короткий ответ:

То, что алгоритм имеет log (n) как часть своего анализа, не означает, что дерево задействовано. Например, ниже приведен очень простой алгоритм, который O(log(n)

for(int i = 1; i < n; i = i * 2)
  print "hello";

Как видите, дерево не было вовлечено. Джон также приводит хороший пример того, как бинарный поиск может быть выполнен в отсортированном массиве. Они оба занимают время O (log (n)), и существуют другие примеры кода, которые могут быть созданы или ссылаются. Так что не делайте предположения на основе асимптотической сложности времени, посмотрите на код, чтобы узнать наверняка.

Подробнее о деревьях:

Тот факт, что алгоритм включает в себя «деревья». O(logn) либо. Вам нужно знать тип дерева и то, как операция влияет на дерево.

Некоторые примеры:

• Пример 1)

Вставка или поиск следующего несбалансированного дерева будет O(n).

• Пример 2)

Вставка или поиск следующих сбалансированных деревьев O(log(n)).

Сбалансированное бинарное дерево:

Сбалансированное дерево степени 3:

Дополнительные комментарии

Если у деревьев, которые вы используете, нет способа «балансировать», чем есть большая вероятность, что ваши операции будут O(n) Время нет O(logn). Анкет Если вы используете деревья, которые самимрают, то вставления обычно занимают больше времени, так как уравновешивание деревьев обычно происходит во время фазы вставки.