Complejidad en Algoritmos
Mejorando tiempo en ejecución
Hola a todos, hoy se trata acerca de un punto muy importante a la hora de trabajar con algoritmos, probablemente es algo que no se retoma en primer plano, pero es muy importante a la hora de optimizar e inclusive adoptar las mejores practicas, reflejándose en nuestra calidad como developers.
Veamos un fragmento de código (Syntaxis en Python):
for i in x: print (i)
Aún así de simple, este código, tendrá asignado un tiempo de ejecución en donde el procesamiento será ocupado hasta que este algoritmo termine. A esto lo conocemos como Runtime Complexity y es un atributo de calidad.
Big(O)
Es como nosotros es como denotamos el comportamiento que los algoritmos tienen durante la ejecución en relación a su complejidad.
“Para Mejorar hay que Identificar las debilidades, para Identificar las debilidades hay que Medir y para medir hay que Planear”
Este es un procedimiento que se usa para la mejora de procesos, algoritmos incluidos y es a la que podemos recurrir para poder encontrar y entregar las mejores soluciones a los problemas que nuestros algoritmos buscan resolver.
Tomemos la imagen como nuestro primer ejemplo, aquí podemos observar mediante BigO que el tiempo de ejecución de este algoritmo es el siguiente:
bO(f(x)). K .: para O(n) el tiempo de ejecución es a lo más K.
Que refleja el comportamiento de nuestro algoritmo en relación al tiempo y las actividades que se harán para obtener el resultado y aquí comienza lo importante, una vez identificamos esto, podemos generar un algoritmo que reduzca los pasos y cambie la complejidad, es decir, estamos optimizando e incrementando la calidad de nuestro trabajo.
Tipos
Cuando trabajamos con bO(X), existen patrones comunes para los algoritmos, que se usan en el día a día:
- bO(1): Es un tiempo directo (1:1). Optimo.
- bO(log n): Es un tiempo largo. Bueno.
- bO(√n). Es un tiempo parcialmente largo. Aceptable
- bO(n): Es un tiempo linear. Puede funcionar.
- bO(n * log n): Es un tiempo reducido-no linear. Vas por buen camino.
- bO(n²): Es un tiempo extendido no linear. Necesitamos mejorar.
- bO(n^n): Es un tiempo muy muy extendido. Ni te atrevas, menos en sistemas con operaciones críticas.
- bO(n!): Es un tiempo casi infinito. Los algoritmos no son lo tuyo bro.
Identificando bO(Algoritmo)
Podemos ver desde el optimo hasta el que nos genera una degradación al sistema, es común ver varios de ellos en nuestras funciones y es muy importante entender como obtener el resultado de nuestro algoritmo.
Lo primero que hay que hacer es separar el algoritmo en componentes individuales que representen nuestro flujo.
Supongamos que para ejecutar una operación, nuestro flujo de datos para por 3 elementos y la complejidad de cada uno es la siguiente:
- Flujo 1: Accedemos a un numero de 3 dígitos en un diccionario: bO(1)
- Flujo 2: Separamos los números pares del número: bO(n)
- Flujo 3: Buscamos los numero que terminen con los números pares: bO(n*logn)
El resultado de la complejidad del algoritmo tiende a tomar la forma del algoritmo más lento más la complejidad de los demás componentes, en este caso nuestra complejidad es la siguiente:
bO(n +(n * log n) +1) = bO(n * log n)
El tiempo constante y el linear no afectan el resultado, es decir, no tenemos un acelerador, por ende son descartados, resultando en bO(n * log n).
Una vez que hemos encontrado esto, podemos ver e identificar en nuestros procedimientos, realizar un plan de acción y mejorar.
Usualmente uso estas preguntas para poder definir que necesito hacer para entregar un resultado con la mayor calidad y que claro, se que si mañana encuentro una mejora, la haré:
- ¿Que pasos puedo eliminar que no son necesarios?
- ¿Que pasos puedo unir para ahorrar procesamiento?
- ¿Que efecto tendré si elimino un paso?
- ¿Necesito agregar validaciones adicionales?
Una vez definas tus pasos para accionar.
¡Manos a la obra!
Conclusión
Conocer de que se trata el tiempo de ejecución, es un atributo importante para que podamos entregar nuestro software con la mejor calidad, sin comprometer al sistema mismo y que en un efecto secundario, se verá reflejado en la mejora de nuestros resultados y adopción de mejores prácticas.
Sigue las siguientes ligas para aprender más sobre tiempo de ejecución y ponte manos a la obra.
Nos vemos en la siguiente.
Keep Reading.
