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

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

6 голосов
/ 22 февраля 2010

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

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

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

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

Ответы [ 7 ]

7 голосов
/ 22 февраля 2010

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

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

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

7 голосов
/ 22 февраля 2010

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

3 голосов
/ 22 февраля 2010

В качестве встречного примера:

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

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

2 голосов
/ 22 февраля 2010

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

0 голосов
/ 27 апреля 2016

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

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

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

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

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

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

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

  • Пример 1)

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

enter image description here

  • Пример 2)

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

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

enter image description here

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

enter image description here

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

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

0 голосов
/ 22 февраля 2010

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

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

0 голосов
/ 22 февраля 2010

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

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

  • Поиск элемента в отсортированном массиве с помощью двоичного поиска или сбалансированного дерева поиска.

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

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...