Notación Big O
La notación Big O es una forma de medir la complejidad de un algoritmo. Es una forma de medir cuánto tiempo tarda un algoritmo en ejecutarse en función de la entrada. La entrada es el tamaño de los datos que se le pasan al algoritmo. Por ejemplo, si tiene una lista de 10 elementos, la entrada es 10. Si tiene una lista de 100 elementos, la entrada es 100.
¿Por qué es importante?
La notación Big O es importante porque nos permite comparar algoritmos. Si tenemos dos algoritmos que hacen lo mismo, pero uno es más rápido que el otro, podemos decir que el algoritmo más rápido es mejor. Pero, ¿cómo sabemos cuál es más rápido? Podemos usar la notación Big O para medir la complejidad de cada algoritmo y compararlos.
Notaciones Big O comunes
Hay muchas notaciones Big O diferentes, pero las más comunes son:
| Nombre | Notación |
|---|---|
| Constante | O(1) |
| Logarítmica | O(log n) |
| Lineal | O(n) |
| Lineal logarítmica | O(n log n) |
| Cuadrática | O(n^2) |
| Exponencial | O(2^n) |
| Factorial | O(n!) |
Constante
La notación Big O constante es O(1). Esto significa que el algoritmo tarda el mismo tiempo en ejecutarse, independientemente del tamaño de la entrada. Por ejemplo, si tiene una lista de 10 elementos, el algoritmo tardará el mismo tiempo en ejecutarse que si tiene una lista de 100 elementos.
Logarítmica
La notación Big O logarítmica es O(log n). Esto significa que el tiempo de ejecución del algoritmo depende del logaritmo del tamaño de la entrada. Por ejemplo, los algoritmos de búsqueda binaria siguen la notación logarítmica.
Lineal
La notación Big O lineal es O(n). Esto significa que cuantos más elementos tenga la entrada, el tiempo de ejecución aumenta proporcionalmente. Por ejemplo, recorrer una lista de elementos con un bucle for sigue la notación lineal.
Lineal logarítmica
La notación Big O lineal logarítmica es O(n log n). En este caso el algoritmo rompe la entrada en partes más pequeñas (divide and conquer) y luego realiza una operación en cada parte. Por ejemplo, el algoritmo de ordenación quicksort sigue la notación lineal logarítmica.
Cuadrática
La notación Big O cuadrática es O(n^2). Esto significa que el tiempo de ejecución puede elevarse al cuadrado a medida que aumenta el tamaño de la entrada. Por ejemplo, en una operación con bucles anidados (por lo general) se observa este comportamiento.
Exponencial
La notación Big O exponencial es O(2^n). Esto significa que el algoritmo duplica su tiempo de ejecución cada que añadimos elementos a nuestro conjunto de datos. Por ejemplo, las funciones recursivas que utilizan fuerza bruta suelen tener este comportamiento. Debemos evitar este tipo de algoritmos o buscar una forma de optimizarlos.
Factorial
La notación Big O factorial es O(n!). Esto significa que el algoritmo tiene un tiempo de ejecución casi vertical, cada vez que añadimos un elemento a nuestro conjunto de datos. Debemos evitar este tipo de algoritmos en la medida de lo posible.