En informática, el análisis de algoritmos es una parte muy importante. Es importante encontrar el algoritmo más eficiente para resolver un problema. Es posible tener muchos algoritmos para resolver un problema, pero el desafío aquí es elegir el más eficiente.
Ahora el punto es, ¿cómo podemos reconocer el algoritmo más eficiente si tenemos un conjunto de algoritmos diferentes? Aquí surge el concepto de complejidad espacial y temporal de los algoritmos. La complejidad del espacio y el tiempo actúa como una escala de medición para los algoritmos. Comparamos los algoritmos en función de su espacio (cantidad de memoria) y complejidad de tiempo (número de operaciones).
La cantidad total de memoria de la computadora utilizada por un algoritmo cuando se ejecuta es la complejidad espacial de ese algoritmo. No discutiremos la complejidad del espacio en este artículo (para hacer este artículo un poco más pequeño).
Complejidad del tiempo
Entonces, la complejidad del tiempo es la cantidad de operaciones que realiza un algoritmo para completar su tarea (considerando que cada operación toma la misma cantidad de tiempo). El algoritmo que realiza la tarea en el menor número de operaciones se considera el más eficiente en términos de complejidad de tiempo. Sin embargo, la complejidad del espacio y el tiempo también se ve afectada por factores como su sistema operativo y hardware, pero no los incluiremos en esta discusión.
Ahora, para comprender la complejidad del tiempo, tomaremos un ejemplo en el que compararemos dos algoritmos diferentes que se utilizan para resolver un problema en particular.
El problema es la búsqueda. Tenemos que buscar un elemento en una matriz (en este problema, asumiremos que la matriz está ordenada en orden ascendente). Para solucionar este problema tenemos dos algoritmos:
1. Búsqueda lineal.
2. Búsqueda binaria.
Digamos que la matriz contiene diez elementos y tenemos que encontrar el número diez en la matriz.
const array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; const search_digit = 10;El algoritmo de búsqueda lineal comparará cada elemento de la matriz con search_digit . Cuando encuentre el search_digit en la matriz, devolverá verdadero .
Ahora contemos el número de operaciones que realiza. Aquí, la respuesta es 10 (ya que compara todos los elementos de la matriz). Entonces, la búsqueda lineal usa diez operaciones para encontrar el elemento dado (estos son el número máximo de operaciones para esta matriz; en el caso de la búsqueda lineal, esto también se conoce como el peor caso de un algoritmo).
En general, la búsqueda lineal tomará n número de operaciones en su peor caso (donde n es el tamaño de la matriz).
Examinemos el algoritmo de búsqueda binaria para este caso.
La búsqueda binaria se puede entender fácilmente con este ejemplo:
Fuente: Learneroo
Si intentamos aplicar esta lógica en nuestro problema, primero compararemos search_digit con el elemento medio de la matriz, es decir 5. Ahora, dado que 5 es menor que 10, entonces comenzaremos a buscar el search_digit en los elementos de la matriz. mayor que 5, de la misma forma hasta obtener el elemento deseado 10.
Ahora, intente contar el número de operaciones que tomó la búsqueda binaria para encontrar el elemento deseado. Se necesitaron aproximadamente cuatro operaciones. Ahora, este fue el peor de los casos para la búsqueda binaria. Esto muestra que existe una relación logarítmica entre el número de operaciones realizadas y el tamaño total de la matriz.
número de operaciones = log (10) = 4 (aprox)
para base 2
Podemos generalizar este resultado para la búsqueda binaria como:
Para una matriz de tamaño n , el número de operaciones realizadas por la búsqueda binaria es: log (n)
La notación Big O
En las declaraciones anteriores, vimos que para una matriz de tamaño n , la búsqueda lineal realizará n operaciones para completar la búsqueda. Por otro lado, la búsqueda binaria realizó log (n) número de operaciones (ambas para sus peores casos). Podemos representar esto como un gráfico ( eje x : número de elementos, eje y : número de operaciones).
Fuente: Techtud
En la figura se desprende claramente que la velocidad a la que aumenta la complejidad para la búsqueda lineal es mucho más rápida que para la búsqueda binaria.
Cuando analizamos un algoritmo, usamos una notación para representar su complejidad de tiempo y esa notación es la notación Big O.
Por ejemplo: la complejidad del tiempo para la búsqueda lineal se puede representar como O (n) y O (log n) para la búsqueda binaria (donde, n y log (n) son el número de operaciones).
La complejidad de tiempo o notaciones Big O para algunos algoritmos populares se enumeran a continuación:
- Búsqueda binaria: O (log n)
- Búsqueda lineal: O (n)
- Clasificación rápida: O (n * log n)
- Orden de selección: O (n * n)
- Vendedor ambulante: O (n!)
Conclusión
Realmente agradezco sus esfuerzos si todavía está leyendo este artículo. Ahora, debe estar pensando: ¿por qué es tan importante comprender la complejidad del tiempo?
Sabemos que para una pequeña cantidad de elementos (digamos 10), la diferencia entre la cantidad de operaciones realizadas por búsqueda binaria y búsqueda lineal no es tan grande. Pero en el mundo real, la mayoría de las veces, nos ocupamos de problemas que tienen grandes cantidades de datos.
Por ejemplo, si tenemos 4 mil millones de elementos para buscar, entonces, en el peor de los casos, la búsqueda lineal tomará 4 mil millones de operaciones para completar su tarea. La búsqueda binaria completará esta tarea en solo 32 operaciones. Esa es una gran diferencia. Ahora supongamos que si una operación tarda 1 ms en completarse, la búsqueda binaria sólo tardará 32 ms, mientras que la búsqueda lineal tardará 4 mil millones de ms (es decir, aproximadamente 46 días). Esa es una diferencia significativa.
Esta es la razón por la que estudiar la complejidad del tiempo se vuelve importante cuando se trata de una cantidad tan grande de datos.
Recursos
Algoritmos de Grokking - por Aditya Y Bhargava
Introducción a la notación Big O y la complejidad del tiempo por CS Dojo