настройка бинарного поиска

Question

В бинарном поиске мы делим массив на 2, а затем снова ищем внутри отдельного массива с помощью рекурсивного бинарного поиска.

Теперь вместо двоичного поиска, если я использую троичный поиск, поиск разделит массив на 3. Мои вопросы:

• Будет ли троичный поиск быстрее двоичного или наоборот?
• При каких условиях какой алгоритм будет работать лучше?
• Зависит ли производительность от размера массива?

Answer 1

Ну, это зависит от того, что вы подразумеваете под «быстрее», точно. Говоря асимптотически, они оба выполняются за время O (log n) (технически бинарный поиск выполняется за O (log_2 (n)), тогда как троичный поиск выполняется за O (log_3 (n)), где log_k означает «основание журнала k», однако они отличаются только постоянным коэффициентом, поэтому они оба эквивалентны O (log n)). Таким образом, с точки зрения алгоритмов, эти две функции выполняются в целом за одно и то же время (т. Е. Имеют одинаковую сложность времени).

Тем не менее, есть, конечно, особый случай, когда один из них потребует меньше вычислений, чем другой. Например, если целевое значение находится точно в середине массива, бинарный поиск вернет значение при первой итерации и никогда не будет повторяться, в то время как троичному алгоритму придется возвращаться, чтобы найти значение. Точно так же, если целевое значение находится на одной трети пути через массив, троичный поиск найдет его немедленно, в то время как бинарный поиск должен будет повториться.

Answer 2

Из вики троичное дерево поиска - это троичное дерево, где узлы расположены в порядке по отношению к ключам поиска.Если ключи поиска являются строками, каждый узел хранит один символ, а поиск строки состоит из серии двоичных поисков, по одному для каждого символа в строке:

В двоичном поиске вы просто сравниваете и получаете половинуили другой.
Но в троичном поиске, где вы сравниваете, если оно меньше, вы получаете 1-ю 1/3-ю, иначе снова сравниваете, если меньше, вы получаете вторую 1/3-ю, или же получаете последнюю 1/3rd.

Подробнее здесь:

• Зачем использовать бинарный поиск, если есть троичный поиск?
• Почему вместо этого используется бинарный поисктройного (3 части) поиска?

Answer 3

У меня возникли проблемы с определением того, что вы подразумеваете под "троичным поиском". Причина, по которой двоичный поиск разбивает массив на две половины, состоит в том, что при каждом сравнении, которое вы выполняете, массив разбивается на две области: элементы меньше, чем рассматриваемый элемент, и элементы больше, чем рассматриваемый элемент. Я не вижу простого способа обобщить это так, чтобы вы разбили массив на три части, выполнив одно сравнение.

Однако, если вы не разбиваете массив на равные половины и вместо этого разбиваете его на ¹ / ₃ / ² / ₃ разделите на каждую итерацию, тогда вы все равно получите производительность O (lg n), хотя постоянный член будет выше. На самом деле, для любой постоянной & epsilon; в котором вы разбиваете массив на доли размера & epsilon; / 1- & epsilon; кусочки, вы получите O (LG N) поведение.

Если при выполнении сравнения вы разбили массив на две части размером & epsilon; n и (1- & epsilon;) n, завершив работу только тогда, когда размер массива станет меньше единицы, то алгоритм завершится после k шагов, где k - наименьшее целое число, для которого & epsilon; ^k n <1 и для которого (1- & epsilon;) <sup>k n <1. Переставляя, получаем </p>

& epsilon; ^k n <1 </p>

& epsilon; ^k <1 / n </p>

k> log _{& epsilon;} 1 / n

k> - log _{& epsilon;} n

k> - lg н / lg & epsilon;

k> lg н / lg ¹ / _{& epsilon;}

Используя аналогичную логику, но с 1 - & epsilon ;, мы получаем, что

k> lg н / lg ¹ / _{(1 - & epsilon;)}

Обратите внимание, что поскольку lg ¹ / _{& epsilon;} и lg ¹ / _{(1 - & epsilon;)} являются константами, наименьшая k, удовлетворяющий этим свойствам, равен O (lg n).

Answer 4

Если вы говорите об однопроцессорной системе, то здесь нет асимптотической разницы и есть дополнительные издержки при троичном поиске.В многопроцессорных / многоядерных системах это (до определенного момента) ускоряет поиск, чтобы разделить его на независимые поиски (при условии, что среда выполнения / язык допускает такое разделение).Но обычно это лучше всего делать на верхнем уровне только один раз.