Почему бинарный поиск быстрее, чем троичный?

Поиск массив элементов с помощью бинарного поиска дублей, в худшем случае итераций , потому что на каждом шаге мы подрезать половину нашего пространства поиска. Если бы вместо этого мы использовали «троичный поиск», мы бы вырезали две трети пространства поиска на каждой итерации, поэтому в худшем случае должно быть итераций ... $N$ $\log_2 N$ $\log_3 N < \log_2 N$

Кажется, что троичный поиск быстрее, так почему мы используем бинарный поиск?

algorithms algorithm-analysis runtime-analysis search-algorithms binary-search Средняя площадь
источник

Разве нельзя использовать те же рассуждения о четвертичном поиске? Или даже десятичный поиск ... или что-нибудь большее, чем 2.

d'alar'cop

пожалуйста, прочитайте о деревьях B +

arunmoezhi

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

псевдоним

Также 2 * log_3 (N) = log_3 (N ^ 2), если он говорит с вашей интуицией.

PawelP

Давайте изложим это в интуитивно понятных терминах. Если использование поиска на основе 3 быстрее, потому что оно сокращает пространство поиска на каждой итерации, то не будет ли поиск на основе миллиона быстрее? Но вы можете легко увидеть, что в среднем вам придется делать 500 000 проверок внутри каждой итерации, чтобы определить 1-миллионный фрагмент, содержащий цель. Очевидно, что сокращение пространства поиска пополам на каждой итерации и не более дает вам больше информации за один шаг, надежно.

ErikE

Ответы:

\log_{2} (n) + O (1)

$\log_2(n)+O(1)$

2 \cdot \log_{3} (n) + O (1)

$2 \cdot \log_3(n) + O(1)$

2 \cdot \log_{3} (n) + O (1) = 2 \cdot \frac{\log (2)}{\log (3)} \log_{2} (n) + O (1)

$2 \cdot \log_3(n) + O(1) = 2 \cdot \frac{\log(2)}{\log(3)} \log_2(n)+ O(1)$

2 \cdot \frac{\log (2)}{\log (3)} > 1

$2 \cdot \frac{\log(2)}{\log(3)} > 1$

$n$

$n$ $f(k) = (k-1) \cdot \frac{\log(2)}{\log(k)}$ $k$

DCTLib
источник

И LHS является линейным, а RHS является логарифмическим, поэтому он не поможет ни для четвертичного периода, ни для чего-то большего ... Хорошие объяснения .... Спасибо

The Mean Square

Просто для полноты: обратите внимание, что абстрактная мера, такая как число сравнений элементов, может или не может доминировать в реальном времени выполнения. В частности, вам, возможно, придется учитывать, сколько промахов в кеше вы, вероятно, получите при длинных массивах при любом поиске. (Здесь они совпадают. Я просто отмечаю это, потому что ОП спрашивает: «Почему это быстрее?», И отвечая на это с помощью абстрактной меры, может вводить в заблуждение некоторые алгоритмы.)

Рафаэль

В троичном поиске в 1/3 времени вам понадобится только 1 сравнение (сделайте более низкое сравнение: если в нижней трети вам не нужно второе сравнение). Это делает троичное только на 5% медленнее, чем на 25% (в этом мире, в котором мы заботимся только о количестве сравнений). Я не уверен, как обобщить это на n-ary, хотя я подозреваю, что он никогда не становится быстрее, чем двоичный.

Аарон Дюфур

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

суперкат

@AaronDufour Но вы амортизируете элементы для поиска, и мне не ясно, почему это нормально. В худшем случае оба сравнения могут выполняться на каждом этапе.

Сашо Николов

DCTLib прав, но на секунду забудем математику.

По твоей логике, n- трей должен быть самым быстрым. Но если подумать, n -ary в точности равен обычному итерационному поиску (просто перебирает список 1 на 1, но в обратном порядке). Сначала вы выбираете последний (или рядом с последним) элемент в списке и сравниваете это значение со значением сравнения. Затем вы удаляете этот элемент из своего списка, а затем выбираете последний элемент в новом списке, который находится рядом с последним значением в массиве. Каждый раз вы будете удалять только 1 значение за раз, пока не найдете свое значение.

Вместо этого вы должны думать об этом так: как мне исключить большинство значений из списка на каждой итерации? В бинарном поиске вы всегда исключаете половину списка. При троичном поиске есть вероятность (на самом деле 33,33%), что вы можете удалить 2/3 списка, но есть еще больший шанс (66,66%), что вы удалите только 1/3 списка. чтобы рассчитать O (n), вам нужно взглянуть на сценарий наихудшего случая, который равен 1/3, меньше 1/2. По мере того, как вы все ближе и ближе, становится еще хуже.

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

(P_lower) x (часть, которую мы можем удалить, если она ниже) + (P_higher) x (часть, которую мы можем удалить, если она выше) = E

Для бинарного поиска это .5x.5 + .5x.5 = .5 (мы всегда удаляем половину списка). Для троичных поисков это значение равно .666x.333 + .333x.666 = 0.44, или на каждом шаге мы, вероятно, удалим только 44% списка, что делает его в среднем менее эффективным, чем бинарный поиск. Это значение достигает пика 1/2 (половина списка) и уменьшается по мере приближения к n (обратная итерация) и 0 (обычная итерация).

Ладно, я солгала ... тут немного математики, но я надеюсь, что это поможет!

dberm22
источник

Это отличный ответ.

The_Sympathizer

Я анализ границ помогает понять сложную математику! n-арный последовательный поиск имеет ту же стоимость, что и линейный поиск O (n).

Шува

-2

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

Джошуа
источник

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

FrankW

Сравнения не будут лишними, и проблема не имеет ничего общего с компилятором. Чтобы разделить пространство поиска на три части, вам нужно 2 сравнения. В бинарном поиске вам нужно сравнить только со средним элементом, и вы затем узнаете, в какой половине пространства поиска будет находиться результат. При троичном поиске вам нужно сравнить с элементом 1/3 пути через список И один 2/3 пути через список. Какой тип данных вы сравниваете или какой язык вы используете, не имеет значения. Конечно, если предмет находится на 1-ом месте, вы можете остановиться после 1 сравнения.

Рейраб

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

JPA

Черт возьми - неправильное определение троичного поиска.

Джошуа