¿Por qué la búsqueda binaria es más rápida que la búsqueda ternaria?

La búsqueda de una matriz de elementos usando la búsqueda binaria toma, en el peor de los casos, iteraciones porque, en cada paso, recortamos la mitad de nuestro espacio de búsqueda. Si, en cambio, utilizamos 'búsqueda ternaria', cortaríamos dos tercios de nuestro espacio de búsqueda en cada iteración, por lo que el peor de los casos debería tomar iteraciones ... $N$ $\log_2 N$ $\log_3 N < \log_2 N$

Parece que la búsqueda ternaria es más rápida, entonces, ¿por qué usamos la búsqueda binaria?

algorithms algorithm-analysis runtime-analysis search-algorithms binary-search El cuadrado malo
fuente

¿No podría uno usar el mismo razonamiento sobre la búsqueda Cuaternaria? O incluso búsqueda decimal ... o algo más grande que 2.

d'alar'cop

por favor lea sobre B + Trees

arunmoezhi

La búsqueda lineal a menudo es más rápida que la búsqueda binaria en problemas de tamaño pequeño a mediano en hardware moderno, porque es coherente en caché y casi todas las ramas se predicen correctamente.

Seudónimo

También 2 * log_3 (N) = log_3 (N ^ 2) si habla a su intuición.

PawelP

Pongamos esto en términos intuitivos. Si usar una búsqueda basada en 3 es más rápido porque reduce más el espacio de búsqueda en cada iteración, ¿no está usando una búsqueda basada en millones más rápido? Pero puede ver fácilmente que, en promedio, tendría que hacer 500,000 comprobaciones dentro de cada iteración para determinar la porción número 1 millón que contenía el objetivo. Claramente, reducir el espacio de búsqueda a la mitad en cada iteración y no más, le brinda la mayor cantidad de información en un solo paso, de manera confiable.

ErikE

Respuestas:

Si aplica la búsqueda binaria, tiene muchas comparaciones. Si aplica la búsqueda ternaria, tiene muchas comparaciones, ya que en cada paso, debe realizar 2 comparaciones para cortar el espacio de búsqueda en tres partes. Ahora, si hace los cálculos, puede observar que: Como sabemos que , en realidad obtenemos más comparaciones con la búsqueda ternaria.

\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$

Por cierto: búsqueda ary puede hacer mucho sentido en el caso si las comparaciones son bastante costosos y pueden ser paralelizados, como entonces, las computadoras paralelas se pueden aplicar. $n$

Tenga en cuenta que el argumento se puede generalizar para búsqueda ary con bastante facilidad. Solo necesita mostrar que la función es estrictamente monótona y aumenta para los valores enteros de . $n$ $f(k) = (k-1) \cdot \frac{\log(2)}{\log(k)}$ $k$

DCTLib
fuente

Y LHS es lineal y RHS es logarítmico, por lo que no ayudará en ningún cuaternario o algo más que eso ... Buenas explicaciones ... Gracias

The Mean Square

Solo por completar: tenga en cuenta que una medida abstracta como el número de comparaciones de elementos puede o no dominar el tiempo de ejecución real. En particular, es posible que tenga que considerar cuántos errores de caché es probable que obtenga en matrices largas con cualquiera de las búsquedas. (Aquí, coinciden. Solo estoy notando esto porque el OP pregunta, "¿por qué es más rápido?", Y responder eso con una medida abstracta puede ser engañoso para algunos algoritmos.)

Raphael

En una búsqueda ternaria, 1/3 de las veces solo necesitará 1 comparación (haga una comparación más baja: si en el tercio inferior, no necesita la segunda comparación). Eso hace que el ternario sea solo un 5% más lento en lugar del 25% (en este mundo en el que solo nos importa el conteo de comparación). No estoy seguro de cómo generalizar esto a n-ary, aunque sospecho que nunca es más rápido que el binario.

Aaron Dufour

@AaronDufour: Dado que uno podría hacer una búsqueda cuaternaria al comparar primero con el elemento del medio y luego ignorar el resultado de las otras comparaciones, la única forma en que la búsqueda cuaternaria podría ser más rápida sería si se pudieran hacer tres comparaciones en paralelo de manera más económica que dos comparaciones podría realizarse de forma secuencial.

supercat

@AaronDufour Pero está amortizando los elementos a buscar, y no me queda claro por qué eso está bien. En el peor de los casos, ambas comparaciones se pueden realizar en cada paso.

Sasho Nikolov

DCTLib tiene razón, pero olvida las matemáticas por un segundo.

Por su lógica, entonces, n -ary debería ser el más rápido. Pero si lo piensa, n -ary es exactamente igual a una búsqueda de iteración regular (solo iterando a través de la lista 1 por 1, pero en orden inverso). Primero, selecciona el último (o penúltimo) elemento de la lista y compara ese valor con tu valor de comparación. Luego, elimina ese elemento de su lista y luego elige el último elemento de la nueva lista, que es el penúltimo valor de la matriz. Cada vez, solo estaría eliminando 1 valor a la vez hasta que encuentre su valor.

En cambio, debería pensarlo así: ¿cómo elimino la mayoría de los valores de la lista en cada iteración? En una búsqueda binaria, siempre elimina la mitad de la lista. En una búsqueda ternaria, existe la posibilidad (33.33% de probabilidad, en realidad) de que pueda eliminar 2/3 de la lista, pero hay una posibilidad aún mayor (66.66%) de que solo elimine 1/3 de la lista. para calcular O (n), debe mirar el peor de los casos, que es 1/3, menos de 1/2. A medida que te acercas más y más a n, empeora aún más.

No solo se mejorará el peor de los casos con la búsqueda binaria, sino que también se mejorará su tiempo promedio . Mirando el valor esperado (qué porción de la lista podemos eliminar en promedio), usamos esta fórmula:

(P_lower) x (parte que podemos eliminar si es inferior) + (P_higher) x (parte que podemos eliminar si es superior) = E

Para la búsqueda binaria, esto es .5x.5 + .5x.5 = .5 (siempre eliminamos la mitad de la lista). Para búsquedas ternarias, este valor es .666x.333 + .333x.666 = 0.44, o en cada paso, es probable que solo eliminemos el 44% de la lista, por lo que es menos eficiente que la búsqueda binaria, en promedio. Este valor alcanza su punto máximo en 1/2 (la mitad de la lista) y disminuye a medida que se acerca a n (iteración inversa) y 0 (iteración regular).

Ok, entonces mentí ... hay un poco de matemática involucrada, ¡pero espero que ayude!

dberm22
fuente

Esta es una respuesta genial.

The_Sympathizer

¡El análisis de límites ayuda a entender las matemáticas difíciles! La búsqueda secuencial n-aria tiene el mismo costo de la búsqueda lineal O (n).

shuva

-2

Tenga en cuenta que el argumento de comparación log (N) vs 2 log (N) se basa en una interpretación ingenua del algoritmo. Si realmente me sentara y escribiera esto en el ensamblaje x86, los resultados se invertirían. El problema es el uso de enteros para casos de prueba combinados con un compilador insuficientemente inteligente que no puede eliminar las comparaciones redundantes. Vuelva a intentar con cadenas y una función de comparación de cadenas apropiada, y codifíquelo para llamar a la función de comparación una vez por ciclo y encontrará que la búsqueda ternaria es más rápida nuevamente.

Joshua
fuente

Por supuesto, la búsqueda ternaria sería más rápida si pudiera hacerlo con solo una comparación por iteración. Pero, no importa si son cadenas o enteros, no puedes.

FrankW

Las comparaciones no serían redundantes y el problema no tiene nada que ver con el compilador. Para dividir el espacio de búsqueda en tres partes, necesita 2 comparaciones. En una búsqueda binaria, solo necesita comparar con el elemento del medio y luego sabe en qué mitad del espacio de búsqueda se ubicaría el resultado. Con la búsqueda ternaria, necesitaría comparar con el elemento 1/3 del camino a través del lista Y el 2/3 del camino a través de la lista. Qué tipo de datos está comparando o qué idioma está utilizando es irrelevante. De acuerdo, si el artículo está en el 1er 3ro, puedes parar después de 1 comparación.

reirab

En algunas plataformas, la búsqueda ternaria podría ser más rápida debido a que la CPU tiene más tiempo para buscar los operandos de la RAM antes de necesitarlos para compararlos. Pero eso depende totalmente de la plataforma utilizada y sus latencias y cachés.

jpa

Maldita sea: definición incorrecta de búsqueda ternaria.

Joshua