Почему поиск в BST быстрее, чем алгоритм двоичного поиска

Question

Интересно, почему поиск в BST быстрее, чем алгоритм двоичного поиска.

Я говорю о дереве, в котором (почти) всегда одинаковое количество векторов в поддереве (хорошо сбалансировано).

Я проверил их обоих, и поиск в BST всегда быстрее.Почему?

Answer 1

Невозможно узнать, не глядя на реализацию. По своей сути они одно и то же.

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

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

Answer 2

Оба должны быть примерно одинаковыми с точки зрения скорости. Оба являются O (log n). Бинарный поиск обращается к ячейке памяти и производит сравнение на каждой итерации. BST следует за указателем (который также является доступом к памяти) и производит сравнение. Разница в константах в их сложности Big-O должна быть незначительной.

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

mid=(high+low)/2;

Операция деления может быть дорогостоящей по сравнению с целочисленными операциями сложения и сравнения. Это может способствовать увеличению производительности. Одним из способов уменьшения воздействия будет использование:

mid=(high+low)>>1;

Но я думаю, что большинство компиляторов все равно оптимизируют это для вас.

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

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