¿Alguna
vez te has preguntado sobre la eficiencia de tu código programado? En esta
ocasión explicaremos sobre Big O (también llamado O grande / O mayúscula).
La O
mayúscula es una notación matemática que nos ayuda a describir el
comportamiento de una función “al límite”. Esta notación tiene muchos usos en
realidad, sin embargo, el que nos interesa ahora es el que se le da en las
Ciencias de la Computación.
En las ciencias de la computación esta notación nos ayuda a describir
el comportamiento de un algoritmo, ya sea temporal (cuantas unidades de tiempo
va a tardar en ejecutarse) o en espacio (cuanta memoria va a ocupar mientras se
ejecuta), esto basado en la cantidad de entradas que recibe y sobre los que
opera. A este "comportamiento" también se le conoce como complejidad
de un algoritmo. Este análisis de complejidad nos sirve generalmente cuando las
entradas de el algoritmo analizado son muy grandes.
En un ejemplo directo aplicado sería buscar un valor dentro
de un arreglo de enteros ordenado (de seguro ya tienes una solución para dicho
algoritmo) pero analicemos por partes (queremos buscar el valor 26) en la
siguiente cadena de longitud n=9, plantearemos 2 soluciones:
1.
Si pensamos de “una forma normal” sería fácil;
recorro desde el inicio hasta encontrar el número 26. Si pensamos en “el peor de los casos” sería 9 veces leía
la cadena. Vemos que es igual a N entonces digamos que la complejidad
computacional será de O(n).
2.
Ahora que pasaría si te digo que podríamos hacer
lo siguiente: partimos en 2 la cadena y quedaría de la siguiente forma:
Validamos si el elemento del centro (en
este caso es 18) es menor, igual o mayor que el elemento buscado (26) y
confirmaremos que estará al lado derecho.
Y empezamos a recorrer la mitad de la
derecha y luego aplicamos lo mismo (partimos la cadena nuevamente en dos) hasta
encontrar el resultado ¿Se puede visualizar que es más rápido? En este caso ya
no recorrerá N, sino que en el peor de
los casos será de:
. ¿Cómo lo obtuve? En otro post detalle
este resultado. En lenguaje computación
suelen omitir la base del logaritmo y solo poner:
. Entonces la complejidad de este algoritmo será de O(logn).
En el siguiente gráfico nos mostrará sobre la eficiencia de nuestro algoritmo, claramente el resultado en el punto 2 es lo más óptimo.
Recuerda que hay un tiempo constante “c”, el cual es el
tiempo que la maquina donde lo correrás el algoritmo.
Utilizar Big O, no sólo puede ayudarte optimizar y/o iniciar
la optimización de tu código sino en tener algoritmos mucho más livianos para
que no sufra mucho tus servidores. Otro campo por ejemplo donde recién estoy iniciando
y me gustaría escribir en otro post es en la aplicación en al Bioinformática.
Para concluir, de hoy en adelante cuando alguien te pregunte
la complejidad de tu algoritmo. Lo que espera es una expresión Big O, como el
tamaño de conjunto de datos afecta el rendimiento del tamaño del algoritmo.
Espero te haya servidor de ayuda y publicará algunos ejemplos en siguientes
post.
Fuentes importantes de extracción de información para este
post:
http://www.cs.us.es/~jalonso/cursos/i1m/temas/tema-28.html
https://thatcsharpguy.com/post/notacion-o-grande/
https://codingbackside.wordpress.com/2018/06/24/big-o-notation/
https://www.asanzdiego.com/2018/12/la-notacion-o-grande-con-ejemplos-en-javascript.html
