Algoritmos: Big O
En palabras llanas podemos considerar la Big O como un sistema de clasificación para el comportamiento de nuestros algoritmos en función de la cantidad de datos con los que trabajan. Teniendo lo anterior en mente podemos representar la Big O como una gran fotografía panorámica sin detalles superfluos sobre el comportamiento de un algoritmo en función de sus datos de entrada.
Ejemplo : Tengo 3 marcos de clasificación que son perros, gatos y pollos. Cada imagen de un animal aquí es distinta en sus detalles, pero cada una representa de forma general un tipo de animal. Sin importar sus diferencias en detalle o cantidad yo puedo resumirlas en una simple silueta que indique a que tipo de animal pertenece.
Gato
Perro
Pollo
El ejemplo anterior muestra la idea general detrás del uso de la Big O en la informática. Podemos clasificar los algoritmos sin enfocarnos en detalles superfluos, simplemente viendo su silueta o características esenciales puede decir a que Big O pertenece.
¿Cuáles son los marcos de clasificación que propone la Big O?
Basándonos en el ejemplo anterior nuestros marcos de referencia para clasificar eran tres, la silueta del perro, gato o pollo. En la Big O tenemos de forma resumida 7 marcos de referencia para clasificar nuestros algoritmos. Estos marcos se basan en la cantidad de operaciones que puede realizar un algoritmo en función de los n datos que recibe.
Los 7 marcos para comparar son los siguientes, ordenados de mejor a peor comportamiento:
La variable n representa el número de datos que entra en el algoritmo, k representa una constante.
O(k), O(1); Constante:
Aquí no importa la cantidad de datos que entren el algoritmo resolverá el problema siempre con la misma gráfica sin variación en su comportamiento, con la misma cantidad de operaciones. Principal características no hay ciclos con los datos de entrada n.
O(log(n)); logarítmica:
Al igual que la anterior el cambio de la gráfica es pequeño, depende de la base del logaritmo, por ejemplo si es base 10, el resultado de introducir 100 datos sería 2 operaciones; el resultado de introducir 1000 sería 3 operaciones, el comportamiento del algoritmo sería logarítmico. Por lo general, los algoritmos de búsqueda tienen log n si están ordenados (búsqueda binaria).
O(n); Lineal:
La grafica o silueta de nuestra Big O lineal crece igual operaciones y datos, si le entran 100 datos el algoritmo tendrá que hacer 100 operaciones para resolverlo. Bucle que recorre n elementos.
O(n * log(n)); Constante y logarítmica:
Este es el último de los algoritmos con un comportamiento aceptable, mezcla las características de los dos tiempos anteriores. Multiplica la relación logarítmica y la lineal. Generalmente operaciones de clasificación
O(n^k), O(n^2) :
Esta es la primera de las siluetas donde los algoritmos peor se comportan. 10 datos se pueden transformar fácilmente en 100 operaciones. Cada elemento de una colección debe compararse con cualquier otro elemento, normalmente vemos ciclos anidados.
O(k^n), O(2^n):
Esta es una silueta con un cambio mucho más rápido que la anterior, ejemplo para 10 datos puedes subir rápidamente a 1024 operaciones. Algoritmos recursivos que resuelven un problema de tamaño N.
O(n!):
Este es peor comportamiento que pueda tener un algoritmo en esta clasificación, aquí nos dicen la muestra. Aquí podemos tener rápidamente con 10 datos pasamos a 3628800 operaciones. Estás agregando un bucle para cada elemento.
Comentarios
Publicar un comentario