Muy buenas, les saluda Luis y en esta ocasión les traigo otro artículo.
La definición clásica de Big O según Wikipedia es:
La notación Big O es una notación matemática que describe el comportamiento limitante de una función cuando el argumento tiende hacia un valor particular o infinito.
Hay muchos conceptos dentro de esta definición y probablemente por eso mucha gente le tiene miedo a Big O. En pocas palabras, usamos Big O para describir el desempeño de un algoritmo. Esto nos ayuda a determinar si un algoritmo es escalable o no. Esto significa: ¿este algoritmo seguirá funcionando incluso si la entrada se vuelve realmente grande? La verdad es que la mayoría de las veces asumimos que debido a que nuestro código se ejecuta rápido en nuestra computadora, lo hará con la misma rapidez cuando proporcione una entrada más grande. Sin embargo, este no es el caso en absoluto.
Es por eso que usamos la notación Big O para describir el desempeño de un algoritmo. Esto es extremadamente importante cuando se trata de elegir qué estructura de datos usar. Algunas operaciones pueden ser más o menos costosas según la estructura de datos que usemos. Por ejemplo, acceder a una matriz por su índice es muy rápido, pero las matrices tienen una longitud fija. Lo que significa que necesitan cambiar su tamaño cada vez que agregamos un elemento. Esto puede resultar muy costoso si tenemos una gran cantidad de insumos. ¡Veamos algunos ejemplos!
O (1):
public class Main {
public void log(int[] numbers) {
System.out.println(numbers[0]);
}
}
Este método toma una matriz de números enteros e imprime el primer elemento en la consola. En este caso, no importa qué tan grande sea la matriz. Todavía estamos imprimiendo el primer elemento de la matriz. Este método tiene una sola operación y requiere una cantidad constante de tiempo para ejecutarse. Por eso, representamos este tiempo constante de ejecución diciendo que este método tiene un Big O de 1 u O (1). En este ejemplo, el tamaño de la entrada no importa, este método siempre se ejecutará en tiempo constante o en Big 0 de 1. Ahora bien, ¿qué pasa si tenemos dos, tres o cien operaciones que se ejecutan en tiempo constante?
public class Main {
public void log(int[] numbers) {
System.out.println(numbers[0]);
System.out.println(numbers[0]);
System.out.println(numbers[0]);
}
}
En este caso, casi parece obvio pensar que describiría este método como Big O de 3 u O (3). Sin embargo, cuando hablamos de la complejidad del tiempo de ejecución, realmente no nos importa la cantidad de operaciones, solo queremos saber cuánto se ralentiza un algoritmo a medida que crece la entrada. Entonces, en este ejemplo, ya sea que tengamos uno, tres o un millón de elementos, nuestro método se ejecuta en tiempo constante o Big O (1).
O(n):
Aquí tenemos un ejemplo un poco más complejo:
public class Main {
public void log(int[] numbers) {
for (int i = 0; i < numbers.length; i++) {
System.out.println(numbers[i]);
}
}
}
¡Tenemos un bucle! Estamos iterando sobre todos los elementos de la matriz e imprimiendo cada elemento en la consola. Aquí es cuando importa el tamaño de la entrada. Si tenemos un solo artículo vamos a tener una operación de impresión, si tenemos un millón de artículos vamos a tener un millón de operaciones de impresión. Entonces, el costo de estos algoritmos crece linealmente y en correlación directa con el tamaño de la entrada. Representamos la complejidad en tiempo de ejecución de este algoritmo como 0 (n), donde n representa el tamaño de la entrada. A medida que n crece, el costo también aumenta.
O(n²):
En el ejemplo anterior, repasamos un solo bucle, pero ¿qué pasa si tenemos bucles anidados?
public class Main {
public void log(int [] numbers) {
for (int first : numbers)
for (int second : numbers)
System.out.println(first + ", " + second);
}
}
En ambos bucles, estamos iterando sobre todos los elementos de la matriz. Lo que significa que tanto el ciclo externo como el interno tienen una complejidad en tiempo de ejecución de 0 (n). La complejidad en tiempo de ejecución de la función en su conjunto sería O (n²). Debido a esto, decimos que este algoritmo se ejecuta en tiempo cuadrático.
Los algoritmos que se ejecutan en O (n²) son más lentos que los algoritmos que se ejecutan en O (n). Por supuesto, esto depende del tamaño de la entrada. Si tuviera que ejecutar ambas funciones con una matriz de 50 elementos, lo más probable es que no hubiera ninguna diferencia en el tiempo. Pero a medida que la entrada es cada vez más grande, los algoritmos que se ejecutan en O (n²) se vuelven cada vez más lentos.
O(log n):
La última tasa de crecimiento de la que vamos a hablar es el crecimiento logarítmico que mostramos como O (log n). Un algoritmo que se ejecuta en tiempo logarítmico es más escalable que un algoritmo que se ejecuta en tiempo lineal o cuadrático.
Como puede ver arriba, al contrario que la curva lineal, la curva logarítmica se ralentiza en algún punto. Un ejemplo sencillo para mostrar esto es comparar la búsqueda lineal con la búsqueda binaria. Digamos que tenemos una matriz de números ordenados del 1 al 10 y queremos encontrar el número 10. Una forma de encontrar el 10 es usar la búsqueda lineal. Necesitaríamos iterar sobre cada elemento de la matriz hasta encontrar el número 10. Ahora, para que podamos encontrar el número 10, necesitaríamos verificar cada elemento en la matriz y esto puede resultar costoso muy rápido.
Cuantos más elementos tengamos, más nos va a llevar esta operación. La complejidad del tiempo de ejecución de este algoritmo aumenta linealmente y en proporción directa con la entrada. Por otro lado, tenemos una búsqueda binaria que se ejecuta en tiempo logarítmico. Esto es mucho más rápido que la búsqueda lineal. Suponiendo que la matriz está ordenada, comenzamos mirando el número en el medio y verificando si es menor o mayor que el valor que estamos buscando. Dado que 5 es menor que 10, ahora miramos la parte derecha de la matriz y hacemos lo mismo. Continuamos con este patrón reduciendo la búsqueda a la mitad cada vez. Con este algoritmo, si tenemos una matriz de un millón de elementos, podemos encontrar el valor objetivo con un máximo de 19 comparaciones.
Espero que esto aclare un poco más el concepto de Big O y que ahora pueda comenzar a pensar en la complejidad del tiempo de ejecución al diseñar nuevos algoritmos.
Codificación feliz.
Añadir comentario