Análisis de algoritmos
Digamos que tenemos un problema P para el cual necesitamos desarrollar un algoritmo A que solucione a P. Una persona sin mucha experiencia en la industria del desarrollo del software podría codear miles de algoritmos para ese mismo problema; sin pensarlo mucho, con que tan solo obtengan el output correcto. Sin embargo, esto puede que funcione para problemas con inputs relativamente pequeños pero cuando esos algoritmos son usados industrialmente, el análisis entre los algoritmos sí pesa.
Con el análisis de algoritmos, podemos darnos una idea de qué tan rápido va a terminar el algoritmo, qué tan optimizado está, qué tanto necesita de espacio en memoria, entre otros aspectos. Para ilustrar lo anterior, supongamos que tenemos el siguiente problema:
Problema 1. Dado un array arr de números enteros y un valor k, encontrar los índices i y j del array arr tal que arr[i]+arr[j]=k.
Si ustedes se van por una solución rápida (y naive) para el Problema 1, podríamos hacer que el algoritmo A tenga el siguiente enfoque: analizar todos los elementos contra todos, es decir, tomar arr[0] y validar si la suma arr[0]+arr[1,…,n-1]=k, para después tomar arr[1] e ir haciendo esa comparación todo el array.
El enfoque del algoritmo A es válido, pero resulta que podemos hacer otro algoritmo B el cual a diferencia del pasado, tenga la siguiente técnica: haciendo uso de una hashtable, podemos revisar si se encuentra la diferencia del actual elemento (que estamos iterando) y k. Es decir, en la primera iteración, mapeamos el índice (0) de arr con la diferencia arr[0]-k y lo guardamos en la hashtable. Con esto, podemos preguntar siempre si arr[i]-k se encuentra en la hashtable, si es así, el algoritmo se detiene y devuelve los índices, de lo contrario, sigue iterando hasta encontrar o fallar.
Bien, algunos ya se podrán dar cuenta la diferencia entre A y B, si no la ven, déjenme explicarles. Con A, el checar cada elemento con los otros, estamos haciendo un total de n(n-1)/2 iteraciones, siendo n el tamaño de elementos en arr; sin embargo, con el algoritmo B estamos haciendo un total de n iteraciones. Si ustedes comparan, es mucho más barato (o va a trabajar menos la computadora) el algoritmo B.
Complejidad de tiempos
La complejidad de tiempos (o time complexity como es mayormente conocido) significa en pocas palabras el trabajo que tiene que hacer el algoritmo para llegar a la solución.
Para ello se utilizan las notaciones asintóticas. Una muy conocida es la Big O. Esta función nos brinda la cota máxima que nuestro algoritmo puede tener de complejidad en tiempos, sin embargo, en industria, esta función debe ser lo más apegada posible a la función del algoritmo (más como Big Theta, pero no cubriremos más funciones debido que tendríamos que profundizar bastante). Además, Big O desprecia números constantes a excepción del 1 y toma en cuenta solamente variables clave.
La siguiente tabla muestra las funciones más importantes, las cuales son: O(1), O(n),O(n² ),O(n³ ),O(n^n ),O(logn),y O(√n).
Esto nos muestra que si un algoritmo A tiene una complejidad de O(n), con inputs relativamente largos (y que se utilizan en industria) nunca será más pesado que un algoritmo A’ con complejidad O(n^n).
Para ilustrar, las funciones Big O de los algoritmos A y B de la sección pasada son los siguientes: como el algoritmo A que mencionamos que hace un total de n(n-1)/2 iteraciones, y debido que Big O desprecia constantes, su tiempo de complejidad sería de:
y como n²>n entonces el resultado es O(n²).
Para el algoritmo B dijimos que hace un total de n iteraciones, y trivialmente se obtiene su tiempo de complejidad de O(n).
Esto nos dice, a grandes rasgos, que el algoritmo B va a correr en menos tiempo que A para inputs muy grandes.
Conclusión
El análisis de la complejidad de un algoritmo en el que estemos trabajando es muy importante, ya que si el input alguna vez llega a ser más grande de lo normal, un algoritmo como A, podría tardar muchísimo tiempo. Esto nos sirve mucho para mantener nuestras aplicaciones con la mejor optimización posible.
