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.
Contenidos
¿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.
Complejidad temporal Big-O en código Python
Aprende en este proyecto guiado disponible en Coursera sobre la complejidad temporal Big-O aplicado a código Python. Te enseñará a utilizar matplotlib Pyplot para generar un gráfico y visualizar los datos de rendimiento de Big-O, escribir y analizar el rendimiento de una función de ordenación Bubble y a crear una función de búsqueda binaria y realizar un análisis Big-O desde cero.
Preguntas Frecuentes – FAQ
¿Por qué es importante entender la notación Big O?
Entender la notación Big O es importante porque permite a los desarrolladores y científicos de datos evaluar y comparar la eficiencia de diferentes algoritmos. Esto ayuda a elegir el algoritmo más adecuado para una tarea específica, optimizando el rendimiento de aplicaciones y sistemas.
¿Cómo se calcula la notación Big O de un algoritmo?
Para calcular la notación Big O de un algoritmo, se analizan los bucles, bucles anidados, recursiones y operaciones dominantes del código, que son las que más afectan al tiempo de ejecución.
¿Qué significa una complejidad O(1)?
Una complejidad O(1), también conocida como tiempo constante, significa que el tiempo de ejecución del algoritmo es independiente del tamaño de la entrada. No importa cuán grande o pequeña sea la entrada, el tiempo de ejecución permanece constante.
¿Qué representa una complejidad O(n log n)?
Una complejidad O(n log n) representa un algoritmo cuya eficiencia es intermedia entre lineal y cuadrática. Este tipo de complejidad es común en algoritmos de ordenamiento eficientes como Merge Sort y Quick Sort, donde se combina la ordenación (O(n)) y la división logarítmica (O(log n)).
Arquitecto de Datos con más de 6 años de experiencia en el sector del Big Data. Autor de cursos de formación en tecnologías Big Data, Cloud y Streaming completados por más de 5000 alumnos en Udemy y otras plataformas. Miembro de la Apache Software Foundation desde 2019.
