PARTE UNO:
UN POCO DE TEORÍA
Es usual ver programadores discutir códigos para saber cual es mejor.
Programadores discutiendo.
Se pueden ver también varios puntos de comparación en estas conversaciones: variables auxiliares,
ciclos, largo del código, complejidad, simplicidad, estructura de memorias utilizadas, etc…
¿Pero realmente estos son los parámetros para determinar cuando un código es mejor que otro? ¿La eficiencia lo es todo? Y apropósito: ¿Qué es la eficiencia? ¿ Se puede medir?
Empecemos por la definición de eficiencia. Y aunque todos ya la sabemos de memoria, vale la pena recordarla para dar un punto de partida a esta reflexión.
Eficiencia: Capacidad de alcanzar los objetivos y metas programadas con el mínimo de recursos disponibles y tiempo, logrando su optimización.
http://es.wikipedia.org/wiki/Eficiencia
Como buen programador, ya vemos a esta definición con ojos desafiantes. ¿Esta bien hecha? ¿Expresa lo que hay que expresar o hay cosas de más?.
Si observamos bien ya vemos que “objetivos” y “metas programadas” son, más que mal, sinónimos y expresan la misma idea, así que digamos que en este pueblo solo hay lugar para uno y a la otra la echamos a volar. Avanzamos un poco, y vemos que dice “el mínimo de recursos disponibles y tiempo”; ¿Pero acaso el tiempo no es un recurso más? Esta siendo redundante por lo tanto repetimos el procesamiento anterior y sacamos uno de los dos. Para terminar el desmembramiento inhumano de la definición vemos una ultima frase: “logrando su optimización”; hay que ponerse serios si estamos diciendo que es “Capacidad de alcanzar los objetivos y metas programadas con el mínimo de recursos disponibles y tiempo”, ¿No es obvio que es para lograr su optimización?
Editando la definición resulta:
“Eficiencia: Capacidad de alcanzar los objetivos con el mínimo de recursos disponibles.”
El lector encontrará seguramente mejores optimizaciones de esta misma frase.
Ahora bien ¿Para que desperdicie todo un párrafo para desmembrar y descuartizar la hermosa definición de Wikipedia? Simple, fue para usarla de ejemplo. Todo programador le busca la 5º pata al gato y eso es lo que hacemos a la hora de optimizar un algoritmo. En este caso primero identificamos las partes de la definición que demostraban redundancia, para hacer la definición más clara y concisa, luego eliminamos las partes que sobraban para hacerla más corta. Es decir escogimos dos parámetros: largo y claridad y comenzamos a optimizar.
Haciendo una analogía de lo anterior, para determinar cual algoritmo es mejor que otro hay que definir parámetros de comparación. Esto lo haremos a través de los recursos que posee un algoritmo al ejecutarse, porque como es bien sabido un algoritmo debe compartir los recursos de la computadora con el resto.
Los recursos de los que disponemos son básicamente 2:
Tiempo de CPU.
Memoria.
La primera herramienta que les voy a presentar viene de la mano de la teoría de la computación, y se llama: Complejidad de un Algoritmo.
Imagen ilustrativa de complejidad.
La teoría de la complejidad computacional es la rama de la teoría de la computación que estudia, de manera teórica, los recursos requeridos durante el cómputo de un algoritmo para resolver un problema. Los recursos comúnmente estudiados son el tiempo (mediante una aproximación al número y tipo de pasos de ejecución de un algoritmo para resolver un problema) y el espacio (mediante una aproximación a la cantidad de memoria utilizada para resolver un problema).
http://es.wikipedia.org/wiki/Complejidad_computacional
Como bien nuestra amiga Wikipedia nos aclara, este estudio es TEORICO, lo que quiere decir como todo en informática, que no siempre nos va a servir para aplicarlo.
ACLARACIÓN: La siguiente explicación pretende ser meramente un pantallazo, para que el lector asimile aunque sea de forma intuitiva un par de conocimientos extras que le servirán luego para comparar algoritmos. (Si se desea investigar sobre el tema recomiendo para empezar el libro Algoritmos Datos y Programas de Guisti. Editorial Pritence Hall)
El objetivo del cálculo de la complejidad de un algoritmo es acercar el comportamiento del mismo a una función matemática en función de una variable.
Primero, este cálculo se logra asignándole a una expresión simple un peso.
Por ejemplo:
| Expresión | Peso |
| X = x+1; | 1 |
| Y+=2 * cos(y) | 4 |
Por lo tanto si calculamos la complejidad de
x+= x + 5;
z+=2*sin(x)+x
Resultaría 5 aproximadamente, pero no nos apuremos, ya que esto es solo a modo ilustrativo y no se hace ni remotamente de esta manera (paciencia).
Algo que tenemos que tener en cuenta es que siempre hay una variable a la que se le da mayor importancia por la naturaleza del algoritmo. Ejemplo:
=>Si se desea ordenar un array la variable más importante va a ser el número de elementos del array.
=>Si se quiere calcular el factorial de un número, la variable de importancia es ese número.
Cabe destacar que cuando se analiza el comportamiento de un algoritmo, se pueden tomar tres enfoques: El mejor caso, el peor caso y el caso promedio. Ilustremos brevemente mediante ejemplos sencillos:
=>Ejemplo de mejor caso: En un algoritmo de búsqueda, que sea el primer elemento el que se busca.
=>Ejemplo de peor caso: En un algoritmo de búsqueda, que sea el último elemento el que se busca.
=>Ejemplo de caso promedio: En un algoritmo de búsqueda que el ítem buscado este en el medio.
En general, y como resulta obvio el análisis se hace pensando en el caso promedio, pero si se quiere se puede tomar otro enfoque.
Ahora que ya sabemos algunas cosas, empecemos con un ejemplo sencillo: Encontrar el Mayor de un array.
Mayor = vector[0] ;
For (i=1;i < n;i+=1 )
If mayor < vector[i] {
Mayor = vector[i]
};
}
La variable de importancia es notoriamente el tamaño del array. La primer sentencia sabemos que pesa 1, sin embargo la descartamos porque en el cálculo de la complejidad se piensa al algoritmo llevado al extremo, es decir, donde la variable de mayo peso importancia tiende a infinito. ( Moraleja: A partir de ahora sabemos que las constantes van a ser despreciables ya que no dependen de la variable principal)
Luego de analizarlo podemos ver que este algoritmo tiene un comportamiento lineal (Vease también que además es un caso especial ya que el peor, el mejor y el caso promedio son el mismo. Queda en el lector responder porque.) Pero a fin de cuentas ¿Cómo llegamos a la conclusión de que este algoritmo tiene un comportamiento lineal?
Si vemos con atención, dentro del ciclo For se encuentra una sentencia, el If. Este se va a ejecutar N veces (en realidad n-1 pero recuerden lo de las constantes), por lo que el valor de complejidad es N* k (k es la constante), y si las constantes son despreciables entonces la Complejidad de este algoritmo es:
C + N * K (Con c y k constantes) = N.
Quiere decir que el recurso de CPU a utilizar por el algoritmo depende linealmente del tamaño del array.
Conclusión: para el análisis de un algoritmo se debe:
1) Identificar la ( o las) variables de importancia,
2) Despreciar el aporte de las constantes al cálculo.
3) Identificar de que manera la/las variable/s de importancia afectan al consumo de recursos de CPU.
4) Por ultimo identificar en que clasificación de algoritmos se encuentra.
Si el lector todavía se encuentra despierto, notará que mencioné una clasificación de algoritmos. Una vez que se hizo todo el cálculo de complejidad, se puede establecer el posicionamiento del algoritmo en una especie de “ranking”. (En realidad hay que tener en cuenta para esto las asíntotas de la función matemática hallada en comparación a las siguientes, tomando una cota inferior y una superior).
Esta es la lista esta ordenada del más eficiente al menos eficiente:
Constante: El tiempo de ejecución no depende de la variable de importancia por lo tanto es despreciable.
Log N: Crece en forma logarítmica. Ejemplo la búsqueda binaria (más adelante se explicara mejor) donde el problema se divide a cada paso del algoritmo en dos.
N: Como en el caso anterior, el tiempo de ejecución es directamente proporcional a la variable N (variable de importancia).
N Log N: Son ejemplos de algoritmos aquellos que dividen el problema en partes mas pequeñas, pero que al final deben volver a unirlas. Ejemplo: Procesamiento de una imagen.
N^2: El tiempo de ejecución se comporta de manera cuadrática en función de N. Ejemplo: Ordenación bajo el método de la Burbuja.
N^a (a>=2): y en general cualquier polinomio de grado mayor igual a 2. Ejemplo: un algoritmo que devuelva la media y genere ordene la muestra por Burbujeo (obviamente son dos algoritmos pero si lo consideramos uno) seria N^2 + N.
2^N en adelante: Estos son algoritmos casi inaplicables, Ejemplo: El método de fuerza bruta para obtener la contraseña de un archivo.
Supongo que a este punto la cabeza del lector (si es que llego leer hasta aquí) esta un poco confundida, veamos primero el gráfico que compara las distintas “categorías” para comprender mejor lo anterior y luego repasamos un poco lo importante.
En este gráfico la Y representa los ciclos de CPU o simplemente tiempo, y la X representa la variable significativa del algoritmo (N). Se puede apreciar claramente la diferencia de un algoritmo de tipo log(n) a uno del tipo x por ejemplo.
¿Para que ha servido leer este texto? Para conocer que existe una forma teórica para analizar la eficiencia de un algoritmo.
¿Qué es lo que debe quedar claro de la primera parte?
Primero: un algoritmo siempre va a tener una o mas variables que van a influir en la utilización de los recursos de la maquina.
Segundo: A partir de la asignación de un peso y del análisis de ciclos (FOR´s While, DO, Recursividad ) podemos aproximar el comportamiento de un algoritmo a una función matemática.
Tercero: Gracias a la aproximación matemática tenemos un marco para ubicar el algoritmo en estudio dentro de un ranking y de esta manera poder compararlo.
¿Qué viene en Eficiencia. Un asunto de equilibrio. PARTE DOS?
Lo que sigue en esta entrega de cuatro partes, es la explicación mas detallada de cómo efectuar el análisis de complejidad en casos reales con ejemplos. La aplicación de lo aprendido en la realidad practica, y un par de consejos para el momento de implementar código.
¿Qué viene en Eficiencia. Un asunto de equilibrio. PARTE TRES?
En la tercer entrega de este escrito, se encuentran un conjunto de consejos para hacer un algoritmo más eficiente, y consejos prácticos para el momento de implementar.
¿Qué viene en Eficiencia. Un asunto de equilibrio. PARTE CUATRO?
La conclusión de las partes anteriores, donde conclusión es distinta de resumen (aunque seguramente incluya alguno) y agrego un punto de comparación más que en las entregas anteriores estoy ignorando.
Espero que a alguien le sirva esto, y no se olviden de comentar así me animan a seguirlo!
. ( A excepción del jefe que debe recibir 3 
