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:
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.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!
Índice
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, sólo 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.
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.
Gracias por leer este artÃculo. Codificación feliz.
Añadir comentario