Big-O en Español Parte 4
Este es el último de los Post sobre la notación Big-O, vamos a revisar los distintos tipos de rendimientos de cada uno de los tipos de expresión y vamos a ver como combinar las diferentes complejidades.
Los posts anteriores fueron
- Parte 1 - Expresiones Lineares y Constantes
- Parte 2 - Expresiones Cuadráticas, cubicas y de otras potencias
- Parte 3 - Expresiones Logarítmicas, Exponenciales y Factoriales
Grafico de complejidad de Big-O
Referencia:Bigocheatsheet
Como se muestra en el Análisis y lo fuimos revisando en los posts anteriores, las expresiones constantes y algorítmica son las de mejor rendimiento y las exponenciales y factoriales las de peor rendimiento
Veamos la complejidad de estos algoritmos con números
| Notación Big O | 10 elementos | 100 elementos | 1000 elementos |
|---|---|---|---|
| O(1) | 1 | 1 | 1 |
| O(n) | 10 | 100 | 1000 |
| O (log n) | 1 | 2 | 3 |
| 0 (n^2) | 100 | 10000 | 1000000 |
| 0 (2^n) | 1024 | 12676506e+30 | 10715086071862673e +301 |
| O (n!) | 3628800 | 933 e+167 | Infitito |
Como se puede ver y se revisó en los posts anteriores, a mayor cantidad de elementos, el algoritmo demora mucho más tiempo, cabe destacar que estos no son números expresados en segundos, de hecho, en la actualidad, los procesadores son capaces de procesar algoritmos mal diseñados en cuestión de milisegundos, pero siempre hay que tener en cuenta el número de elementos y el impacto que puede tener en nuestros algoritmos.
Operaciones según el tipo de estructura de datos
La siguiente tabla muestra el tipo de Notación Big0 aplicada a cada una de las estructuras de datos y cuando se utilizan
Referencia:Bigocheatsheet
Si comparamos un Arreglo con una Pila (stack) y con una cola (queue) podemos ver (según la table) que, tanto en el peor de los casos como en el mejor de los casos, el acceso en un arreglo es más optimo que en una cola y una pila, pero insertar y eliminar elementos es más optimo en una pila y una cola, la búsqueda tiene la misma complejidad para los tres 0(n) - Lineal.
Es importante entender este tipo de aspectos al trabajar con las diferentes estructuras de datos.
¿Qué pasa cuando en un código se aplican varias complejidades?
Supongamos que en nuestro algoritmo tenemos
O(1)
O(n)
O(n^2)
O= O(1)+O(n)+O(n2) ==> O(n2)
Siempre se considera la mayor complejidad cuando evaluamos un código, de hecho, si convertimos esta notación en una función matemática
f(x)=1+x+x^2
La grafica nos quedará de la siguiente manera
