Я вижу, как при поиске значения в BST мы оставляем половину дерева каждый раз, когда мы сравниваем node со значением, которое мы ищем.
Однако я не понимаю, почему временная сложность O(log(n)). Итак, мой вопрос:
Если у нас есть дерево из N элементов, почему временная сложность поиска дерева и проверка наличия определенного значения O (log (n)), как мы это получаем?
На ваш вопрос, кажется, хорошо ответил здесь, но, чтобы обобщить в связи с вашим конкретным вопросом, было бы лучше подумать об этом в обратном порядке; "что происходит с временем решения BST при увеличении числа узлов?"
По существу, в BST каждый раз, когда вы удваиваете количество узлов, вы только увеличиваете количество шагов для решения одним. Чтобы расширить это, четыре раза узлы дают два дополнительных шага. Восемь раз узлы дают три дополнительных шага. Шестнадцать раз узлы дают четыре дополнительных шага. И так далее.
База 2 log первого числа в этих парах является вторым числом в этих парах. Это база 2 журнала, потому что это двоичный поиск (вы вдвое сокращаете пространство проблем на каждом шаге).
Для меня самым простым способом было посмотреть на график log2 (n), где n - количество узлов в двоичном дереве. В качестве таблицы это выглядит так:
log2(n) = d
log2(1) = 0
log2(2) = 1
log2(4) = 2
log2(8) = 3
log2(16)= 4
log2(32)= 5
log2(64)= 6
а затем я рисую небольшое двоичное дерево, это идет от глубины d = 0 до d = 3:
d=0 O
/ \
d=1 R B
/\ /\
d=2 R B R B
/\ /\ /\ /\
d=3 R B RB RB R B
Так как количество узлов n в дереве эффективно удваивается (например, n увеличивается на 8, поскольку оно идет от 7 до 15 (что почти удваивается), когда глубина d идет от d = 2 до d = 3, увеличиваясь на 1.) Таким образом, требуемый дополнительный объем обработки (или требуемое время) увеличивается только на 1 дополнительном вычислении (или итерации), поскольку объем обработки связан с d.
Мы видим, что мы опускаем только один дополнительный уровень глубины d, от d = 2 до d = 3, чтобы найти node, который мы хотим получить из всех узлов n, после удвоения количества узлов. Это верно, потому что мы теперь искали все дерево, ну, половину этого, что нам нужно было искать, чтобы найти node, который мы хотели.
Мы можем записать это как d = log2(n), где d сообщает нам, сколько вычислений (сколько итераций) нам нужно сделать (в среднем) для достижения любого node в дереве, когда в дереве есть n узлов.
Это может быть показано математически очень легко.
Прежде чем представить это, позвольте мне кое-что уточнить. Сложность поиска или поиска в сбалансированном двоичном дереве поиска - O (log (n)). Для двоичного дерева поиска в общем случае это O (n). Я покажу оба ниже.
В сбалансированном двоичном дереве поиска, в худшем случае, значение, которое я ищу, находится в листе дерева. Я в основном перехожу от корня к листу, просматривая каждый слой дерева только один раз - до упорядоченной структуры BST. Поэтому количество поисков, которые мне нужно сделать, - это количество слоев дерева. Следовательно, проблема сводится к нахождению выражения замкнутой формы для количества слоев дерева с n узлами.
Здесь мы сделаем простую индукцию. Дерево с только 1 слоем имеет только 1 node. Дерево из 2 слоев имеет 1 + 2 узла. 3 слоя 1 + 2 + 4 узла и т.д. Шаблон ясен: дерево с k слоями имеет ровно
п = 2 ^ 0 + 2 ^ 1 +... + 2 ^ {K-1}
узлы. Это геометрическая серия, из которой следует
п = 2 ^ к-1,
эквивалентно
k = log (n + 1)
Мы знаем, что big-oh интересуется большими значениями n, поэтому константы несущественны. Следовательно, сложность O (log (n)).
Я дам другой - гораздо более короткий способ показать тот же результат. Поскольку, ища значение, мы постоянно разделяем дерево на две половины, и мы должны делать это k раз, где k - количество слоев, следующее верно:
(n + 1)/2 ^ k = 1,
что означает точно такой же результат. Вы должны убедить себя в том, откуда этот +1 в n + 1, но это нормально, даже если вы не обращаете на него внимания, поскольку мы говорим о больших значениях n.
Теперь обсудим общее двоичное дерево поиска. В худшем случае он совершенно неуравновешен, то есть все его узлы имеют только один ребенок (и он становится связанным списком). См., Например, https://www.cs.auckland.ac.nz/~jmor159/PLDS210/niemann/s_fig33.gif
В этом случае, чтобы найти значение в листе, мне нужно выполнить итерацию по всем узлам, следовательно, O (n).
Последнее замечание состоит в том, что эти сложности справедливы не только для поиска, но и для операций вставки и удаления.
(Я отредактирую свои уравнения с более красивым математическим стилем Latex, когда я доберусь до 10 повторных точек. SO не позволит мне прямо сейчас.)
Всякий раз, когда вы видите время выполнения, в котором есть фактор O (log n), есть очень хороший шанс, что вы смотрите на что-то вроде формы "продолжайте делить размер какого-либо объекта константой" . Так что, вероятно, лучший способ подумать об этом вопросе - так как вы выполняете поиск в двоичном дереве поиска, что именно это происходит, если урезать постоянный коэффициент и что именно та константа?
Для начала представьте, что у вас есть идеально сбалансированное двоичное дерево, что-то похожее на это:
*
/ \
* *
/ \ / \
* * * *
/ \ / \ / \ / \
* * * * * * * *
В каждой точке выполнения поиска вы просматриваете текущий node. Если это тот, который вы ищете, отлично! Вы полностью закончили. С другой стороны, если это не так, вы либо спускаетесь в левое поддерево, либо в правое поддерево, а затем повторяете этот процесс.
Если вы войдете в одно из двух поддеревьев, вы, по сути, говорите: "Мне все равно, что в этом другом поддереве". Вы бросаете все узлы в нем. И сколько узлов там? Ну, с быстрым визуальным осмотром - в идеале, за ним следует хорошая математика - вы увидите, что вы бросаете около половины узлов в дереве.
Это означает, что на каждом этапе поиска вы либо (1) находите node, который вы ищете, либо (2) отбрасываете половину узлов в дереве. Поскольку вы выполняете постоянную работу на каждом шаге, вы смотрите на поведение поведения O (log n) - работа падает на постоянный коэффициент на каждом шаге, и поэтому он может делать это только логарифмически много раз.
Теперь, конечно, не все деревья выглядят так. У деревьев AVL есть свойство fun, которое каждый раз, когда вы опускаетесь вниз в поддерево, вы выбрасываете примерно золотую долю доли всех узлов. Это гарантирует, что вы можете выполнить логарифмически много шагов до того, как закончите узлы - следовательно, высоту O (log n). В красном/черном дереве каждый шаг отбрасывает (примерно) четверть всех узлов, и поскольку вы сокращаетесь с помощью постоянного коэффициента, вы снова получаете нужное время поиска O (log n). Очень забавное дерево scapegoat имеет настраиваемый параметр, который используется для определения того, насколько он сбалансирован, но опять же вы можете показать, что каждый шаг, который вы берете, отбрасывает некоторый постоянный коэффициент, основанный на этом настраиваемом параметре, предоставляя поиск O (log n).
Однако этот анализ ломается для несбалансированных деревьев. Если у вас чисто вырожденное дерево, где каждый node имеет ровно один ребенок, то каждый шаг вниз по дереву, которое вы берете, отбрасывает только один node, а не постоянную долю. Это означает, что время поиска возрастает до O (n) в худшем случае, так как количество раз, которое вы можете вычесть константу из n, равно O (n).