Мне трудно понять, почему попытки имеют время поиска O (1), а двоичные деревья - O (logn).
Я понимаю, что это в основном деревья. Предположим, у меня есть попытка для английского языка, содержащая слова до 16 символов. Время поиска составляет O (16), что упрощается до O (1). Это связано с тем, что каждый узел дерева имеет массив из 26 дочерних элементов (26 букв в алфавите), а извлечение из массива равно o(1). Так что вам просто нужно сделать 16 тяг.
Принимая во внимание, что для двоичного дерева, если у вас есть n элементов (скажем, n очень велико... весь английский алфавит), вы ищете средний элемент, затем середину подраздела в зависимости от того, является ли ваш элемент ниже/выше, тогда подмножество этого и т. д. и т. д. ... в основном деля на два каждый раз, чтобы получить O (логарифмическая база 2 из n).
Логика для каждого понятна. Но я чувствую, что что-то упускаю.
В чем ключевое различие между ними, которое позволяет выполнять поиск за постоянное время, тогда как для двоичных деревьев требуется O (logn)? Не могли бы вы структурировать двоичное дерево так, чтобы оно было в основном тройкой только с двумя дочерними элементами? Я полагаю, что у меня проблемы с определением разницы.
a, двоичные деревья также станутO(1):-) Весь смысл анализа сложности заключается в том, что происходит, когда набор данных становится < i>произвольно большой. - person paxdiablo schedule 29.10.2015