Introducción

En esta publicación vamos a aprender, mediante un ejemplo, lo importante que es poder optimizar nuestros algoritmos y el uso de la notación Big O (visto en una publicación anterior).

Este ejemplo son los algoritmos de búsqueda:

Un algoritmo de búsqueda es un conjunto de instrucciones que están diseñadas para localizar un elemento con ciertas propiedades dentro de una estructura de datos; por ejemplo, ubicar el registro correspondiente a cierta persona en una base de datos, o el mejor movimiento en una partida de ajedrez.

El objetivo es crear una función que hará lo siguiente: Dada una lista de números, tenemos que verificar si un número “n” está dentro de esta lista; además, guardaremos el número de pasos que nos tomó obtener el resultado.

Vamos a crear nuestra función usando dos enfoques: secuencial y binaria. Es necesario guardar el número de pasos, de esta manera compararemos qué enfoque es más óptimo.

Para que funcione nuestra búsqueda binaria, es necesaria que nuestra lista esté ordenada.

El siguiente código ordena una lista usando el algoritmo quicksort, que tiene complejidad n*log(n), tal como lo vimos anteriormente:

Veamos algunos ejemplos:

Búsqueda secuencial

Este es un algoritmo muy sencillo:

En informática, la búsqueda lineal o la búsqueda secuencial es un método para encontrar un valor objetivo dentro de una lista. Ésta comprueba secuencialmente cada elemento de la lista para el valor objetivo hasta que es encontrado o hasta que todos los elementos hayan sido comparados.

El siguiente diagrama de flujo muestra los pasos a realizar:

El código es el siguiente:

Búsqueda binaria

La descripción del algoritmo es el siguiente:

En ciencias de la computación y matemáticas, la búsqueda binaria, también conocida como búsqueda de intervalo medio o búsqueda logarítmica, es un algoritmo de búsqueda que encuentra la posición de un valor en un array ordenado. Compara el valor con el elemento en el medio del array, si no son iguales, la mitad en la cual el valor no puede estar es eliminada y la búsqueda continúa en la mitad restante hasta que el valor se encuentre.

El siguiente diagrama de flujo muestra los pasos a realizar:

El código es el siguiente:

Comparación

Vamos a hacer algunas pruebas para ver el funcionamiento del algoritmo y que muestren el mismo valor: si se encuentra el número mostrar la ubicación, si no se encuentra el número mostrar el mismo mensaje:

En el primer ejemplo, la búsqueda secuencial fue más rápido que el la búsqueda binaria. Pero en el segundo y tercer ejemplo, la búsqueda binaria fue más rápido. Esto puede indicar que, ambos algoritmos son igual de rápidos. Pero no es así.

La gran diferencia se dará en el peor de los casos. Supongamos que tenemos una lista de “n” elementos. La búsqueda secuencial en el peor de los casos, tendrá que realizar “n” validaciones, por lo que su complejidad es de O(n). ¿Pasará lo mismo con la búsqueda binaria? Veamos

Para la búsqueda binaria si no encontramos el número en cada iteración, la lista se reduce a la mitad. En el peor de los casos, tendremos que dividir siempre por la mitad la lista, pero no será necesario comprobar en todos los elementos, ya que en cada iteración, hay elementos que se eliminarán. Esto nos indica que la complejidad es menor que O(n)

Por ejemplo, supongamos que la lista es de longitud 32. Si fallamos en el primer intento, en el segundo intento la lista tendrá longitud 16. Si fallamos en el segundo intento, en el tercer intento la lista tendrá longitud 8. Si fallamos el tercer intento, el cuarto intento tendrá longitud 4. Si fallamos el cuarto intento, el quinto tendrá longitud 2. Por último, si fallamos en el quinto intento, el sexto intento tendrá longitud 1. Los pasos serían: 32 -> 16 -> 8 -> 4 -> 2 -> 1, un total de 5 pasos (mucho menor que los 32 pasos en la búsqueda secuencial).

Si la lista tiene longitud 16, los pasos serían: 16 -> 8 -> 4 -> 2 -> 1, un total de 4 pasos.

Veamos en la siguiente tabla:

Longitud	Número de pasos
1	0
2	1
4	2
8	3
16	4
32	5
64	6
128	7
256	8
512	9
1024	10

Podemos ver de la tabla que este algoritmo tiene una complejidad logarítmica. Por lo que este algoritmo se denota como complejidad O(log(n))

Si con esto no queda claro la ventaja de la búsqueda binaria, el siguiente código lo hará:

El siguiente gráfico muestra el número de pasos que necesita cada algoritmo dependiendo del número de datos:

Podemos ver que la búsqueda binaria es muchísimo más rápido que la búsqueda secuencial.

Conclusión

En esta publicación hemos aprendido, mediante un ejemplo, la importancia de poder optimizar nuestros algoritmos. Puede que para pocos datos no sea necesaria una optimización, pero si creemos que tendremos cada vez más datos (sobre todo en estos tiempos del Big Data), es importante dedicar tiempo para optimizar nuestros algoritmos.

Espero que les haya gustado esta publicación. Ya saben, cualquier comentario es bienvenido y agradecido.