¿Por qué algunos algoritmos son más eficientes que otros? ¿Por qué se prefiere la búsqueda binaria sobre la lineal?

Esa es una muy buena pregunta.

Déjame presentarte un ejemplo.
Suponga que se le pide que encuentre el máximo puntaje de una clase de 100 estudiantes.
Repasas las marcas de cada uno y encuentras el topper. Ahora agrego 100 personas más a la clase y le pido que encuentre el topper nuevamente. Puedes hacer esto de dos maneras.

1. Tome esos 100 estudiantes adicionales en la clase. Pídales a los 200 estudiantes que se paren en una fila para que puedan comenzar desde el principio y encontrar el topper.
2. Ya conoce el topper de los primeros 100, solo encuentre el topper de los siguientes 100 y compare esos 2 y obtenga el topper.

En el primer enfoque, comenzamos de nuevo y comparamos 200 personas. Mientras que en el segundo, solo tuvimos que comparar esas 100 personas adicionales. ¿No crees que será más fácil seguir el segundo enfoque?

Si solo agrego 100 más, el primer enfoque ahora tendrá que comparar 300 personas desde el principio. Mientras que en el segundo enfoque, simplemente comparamos los 100 adicionales y luego comparamos el topper con los 200 topper anteriores.

Este es un ejemplo de algoritmo. Un algoritmo es una idea de cómo se puede resolver un problema fácilmente con un mínimo de recursos, nada más.

En el caso de las búsquedas, la eficiencia está determinada por el número de comparaciones que se necesitan para encontrar el resultado. Considere una lista de 100 números, en orden ascendente. Necesitamos encontrar el número 78. Veamos cómo funcionan las dos búsquedas.

1. Búsqueda lineal: empiezo desde 1, luego 2, pasa de manera lineal para verificar si es 78. Después de 77 elementos, llegamos a 78 y obtenemos nuestro resultado. Tuvimos que hacer 78 comparaciones.
2. Búsqueda binaria: voy directamente al punto medio, compruebo si 78 es mayor o menor que 78. Es mayor, por lo que ahora es lógico buscar ahora en la mitad derecha, en los números mayores que 50. De esta manera, redujimos directamente Nuestro tamaño del problema a la mitad. ahora solo tenemos que buscar los últimos 50 elementos. Nuevamente, apuntamos al medio, si verificamos si el elemento medio 75 es mayor o menor que 78. Es más pequeño, solo lógico verificar números mayores que 75 si queremos encontrar 78. Redujimos nuestro problema inicial a 1/4 en solo 2 comparaciones. Ahora solo tenemos que buscar en los 25 elementos restantes.

Acabamos de ver cómo la búsqueda binaria demostró ser más eficiente en nuestra búsqueda.

Ahora imaginemos, si una comparación tomó 1 minuto para dar resultado. La búsqueda lineal llevaría 78 minutos seguidos. Pero en la búsqueda binaria podemos obtener la respuesta en solo 5 minutos. Claramente, mejores algoritmos nos dan mejores resultados en mejor tiempo.

¿No es pura suerte que encuentres el número que estás buscando?

Si la lista no está ordenada, entonces sí. Tanto la búsqueda lineal como la binaria serían impredecibles como si obtuviéramos resultados. Para datos sin clasificar, la búsqueda lineal sería la opción preferida. Pero aquí, sabíamos que nuestros datos están en orden ascendente, entonces, ¿por qué no aprovecharlos y utilizar la búsqueda binaria?

Para una mejor visualización, consulte Visualización de búsqueda binaria y lineal.

Estoy dando una perspectiva mucho más generalizada en lugar de responder específicamente sobre la búsqueda binaria o lineal. Hay pocas cosas para hacer que su algoritmo sea rápido o tenga un mejor rendimiento. Hay tres etapas para cualquier dato:

1. Preprocesamiento
2. Algoritmo real
3. Postprocesamiento

Y el algoritmo más exitoso en el mundo trabaja en la combinación de estos tres pasos. Por ejemplo, la búsqueda binaria requiere que sus datos ya estén ordenados (preprocesados) antes de operar. Del mismo modo, la búsqueda lineal no tiene ningún requisito. El algoritmo Map-Reduce (Hadoop) se ejecuta solo en el patrón anterior pero de forma repetitiva. La biblioteca de clasificación en idiomas utiliza principalmente la combinación de pocos algoritmos de clasificación.

Pocas cosas más para ayudar a pensar en el algoritmo

1. Tamaño de datos y tipo de datos, la ordenación por inserción funciona mejor si el tamaño de los datos es demasiado pequeño. La ordenación por fusión es mejor si tiene toneladas de RAM disponibles. Quicksort es lo mejor de ambos mundos.

Los algoritmos son solo instrucciones paso a paso para hacer una tarea en particular. Ahora, como programadores, siempre debemos hacer una pregunta: “¿Podemos hacerlo mejor que esto?”.

Algunos algoritmos son mejores que otros debido a los pasos que toman al resolver un problema. Se trata de preservar nuestro Tiempo y Espacio (Memoria).

Al realizar la búsqueda lineal, en el peor de los casos, es posible que necesitemos buscar hasta elementos ‘n’, mientras que si sabemos cómo implementar la búsqueda binaria podemos encontrar fácilmente el elemento (a veces en 1 acierto o al máximo en 0 (lg n ) pasos).

Supongamos que tiene un diccionario de Oxford con usted y desea encontrar el significado de la palabra “picquet”

Ahora, ¿cómo buscas la palabra en el diccionario?

¿Buscará palabra por palabra desde la primera página (que también se llama búsqueda lineal) Si lo hace, tomará semanas o meses.

Una de las formas óptimas de hacerlo es mediante la búsqueda binaria. Puedes encontrar la palabra en menos de un minuto. Piénsalo.