Является ли O (logn) всегда деревом?

Question

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

EDIT: Благодаря вашим комментариям, я понимаю, что divide-conquer и binary tree настолько похожи визуально/концептуально. Я никогда не связывал связь между ними. Но я думаю о случае, когда O (logn) не является алговым словом, в котором есть дерево, которое не имеет свойства дерева BST/AVL/красно-черного.

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

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

Answer 1

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

В некоторых случаях вы можете преобразовывать другие алгоритмы деления и поколений прямо в двоичные деревья (например, комментарии к другому ответу уже пытались утверждать, что бинарный поиск аналогичен). Однако для другого очевидного примера - многодорожее дерево (например, дерево 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 (журнал (п)), но не дерево здесь!

Answer 4

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

Примеров O (LOGN):

• Нахождение элемента в отсортированном массиве с двоичным поиском или сбалансированным деревом поиска.

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

Answer 5

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

Answer 6

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

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

Answer 7

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

Просто потому, что алгоритм имеет журнал (п) как часть его анализа не означает, что дерево участвует. Например, следующий очень простой алгоритм, который является 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). Если вы используете собственные балансировки, тогда вставки обычно занимают больше времени, так как балансировка деревьев обычно происходит во время фазы вставки.