Big-O Para Principiantes — AprenderBigData.com

Cuando buscamos soluciones a problemas, es muy importante tener en cuenta la complejidad del algoritmo y de las funciones que vamos a implementar. Para comparar la eficiencia y el ratio de crecimiento de los algoritmos usamos la notación Big-O.

¿Qué es Big-O?

La Notación Big-O es una forma de medir el tiempo lo bien que escala un programa o un algoritmo y el tiempo que tardará en ejecutar. Esta medición nos resultará muy útil para comparar la eficiencia de dos algoritmos, por ejemplo de ordenamiento. Es válido para cualquier lenguaje de programación.

Big-O no nos proporciona una medición exacta del tiempo de ejecución, sino una evaluación de cómo de rápido se incrementa el tiempo de ejecución en función de los datos de entrada. La evaluación del algoritmo permite clasificarlos en función de su ratio de crecimiento. Varios algoritmos con el mismo ratio de crecimiento se clasificarán con la misma notación.

En términos matemáticos, describe el límite de una función cuando los argumentos de entrada tienden al infinito o a un valor en particular.

Tiempo constante O(1)

En este caso, el tiempo de ejecución permanecerá constante sin importar el tamaño del dataset de entrada. Estas funciones son muy escalables, y podemos determinar que el tiempo siempre será parecido en cualquier ejecución.

Como ejemplo de O(1) tenemos la lectura de los arrays. Estas estructuras de datos nos permiten las operaciones de lectura de cualquiera de sus elementos sin la necesidad de recorrer todo el contenido, por lo que el tiempo de acceso siempre será constante, sin importar el tamaño y el número de elementos que contiene el array.

Tiempo Logarítmico O(log n)

Las funciones O(log n) toman un tiempo de ejecución que depende del logaritmo del tamaño de la entrada de datos. Por ejemplo, los algoritmos que dividen el dataset de entrada en mitades siguen esta notación. La búsqueda binaria, en la que dividimos la lista inicial por la mitad recursivamente hasta encontrar el valor que buscamos es un ejemplo de tiempo logarítmico.

Tiempo Lineal O(n)

El tiempo para ejecutar estas funciones depende directamente del tamaño del dataset de entrada (n). Cuantos más elementos se añadan al procesamiento, el tiempo de ejecución se incrementará proporcionalmente. Las funciones que usan bucles para recorrer los elementos siguen la notación de tiempo lineal.

Tiempo Cuadrático O(n²)

El crecimiento de las funciones con tiempo cuadrático es exponencial, generalmente se observa en las funciones con bucles anidados. Debemos controlar correctamente la cantidad de elementos de entrada que tienen estos algoritmos, ya que el tiempo de ejecución puede descontrolarse rápidamente al tener un crecimiento tan elevado.

Tiempo Exponencial O(2^n)

El tiempo exponencial expresa las funciones cuyo tiempo de ejecución se dobla con cada elemento que añadimos al dataset de entrada. Las funciones que implementan cálculos recursivos con fuerza bruta siguen esta notación, debemos evitar su uso o limitarlo a conjuntos de entrada pequeños para que el tiempo de ejecución sea razonable.

Tiempo Factorial O(n!)

El crecimiento de las funciones con tiempo factorial es casi vertical, cada elemento añadido al dataset de entrada incrementa de forma considerable el tiempo de ejecución. Debemos intentar evitar el uso de las funciones de este tipo en nuestras aplicaciones y solo usarlas en casos de uso controlados.

Originally published at https://aprenderbigdata.com on September 13, 2022.