Algoritmia, Estructuras de Datos

Necesidad de la algoritmia

Dado un problema cualquiera que se desee implementar, habran casi tantas soluciones efectivas, como programadores trabajen en ella.  Sin embargo sólo habrá una solución, que sea la más eficiente. Ésto se debe a que parte de la programación involucra arte y creatividad, y cada persona piensa de manera diferente.
Dado que siempre estamos interesados en reutilizar lo existente, si buscamos una solución para un problema, seguramente encontraremos varias implementaciones, y deberemos elegir una de ellas como la más eficiente para utilizar.

Para ésto, primero tenemos tener claro la diferencia entre efectivo y eficiente:

Efectividad: Capacidad de lograr el efecto que se desea o se espera.

Eficiencia:  capacidad para lograr un fin, empleando los medios más adecuados

Claro, definir "los medios más adecuados" depende de la solución y lo que se declare importante.  Por ejemplo: si se desea ir el país vecino ¿cuál es el medio más adecuado para llegar? ¿por bus, por avión, caminando? Tomar la decisión del medio, dependerá de qué el lo importante que se desee lograr. Si tenemos tiempo y nos gusta disfrutar el paisaje, el mejor medio es el bus, si tenemos un negocio importante que nos perderíamos si no llegaramos a tiempo, el medio adecuado sería el avión.

Eficiencia de algoritmos

Para lograr comparar dos algoritmos tenemos dos opciones:

• Método empírico (a posteriori):Consiste en realizar las dos implementaciones y realizar ejecuciones similares, en la misma máquina y con la misma cantidad de datos, y comparar los tiempos de ejecución. Este método es la medida más exacta que se puede lograr, pero tiene la desventaja es que no siempre hay tiempo para hacer varias implementaciones o, si ya están hechas, hacer ambas implementaciones puede ser compleja y no ser factible.
• Método teórico (a priori): Consiste en realizar un análisis matemático de los algoritmos y determinar una medida de la eficiencia. Ésto tiene la ventaja que no necesita una implementación real de los algoritmos, ya que basta con un esbozo de la implementación  para realizar el análisis.  

En el caso de los algoritmos, los medios para lograr la eficiencia se refieren a la utilización de tiempo y memoria, los cuales se tienen que equilibrar, y nos referimos a ellos en el estudio de complejidad espacial (eficiencia en el uso de la memoria) y complejidad temporal (eficiencia en el tiempo de ejecución).

La complejidad espacial se refiere a cuánta memoria necesita un algoritmo para ejecutarse completamente.   Aunque actualmente se tiene la impresión que no es tan determinante para la construcción de un algoritmo como solía ser, sigue siendo un factor a tomar en cuenta al momento de implementar una solución, principalmente en ambientes concurrentes, como soluciones web, o en ambientes más restringidos como las soluciones móviles.  En el ambiente web, un servicio relativamente simple, si tiene alta complejidad espacial (usa mucha memoria), al atender a miles de clientes, puede colapsar cualquier servidor.   En un ambiente móvil, la memoria es más limitada que en una PC o servidor, por lo que se debe tener presente la cantidad de memoria a utilizar.
Anteriormente, era crítico el análisis de complejidad espacial, ya que si un programa no cabía en memoria (programa más datos) no era posible ejecutarlo.  Actualmente, ésto ya no es restricción debido al uso de la memoria virtual, pero ya que ésta involucra la utilización de disco duro, igualmente se debe vigilar el uso de la memoria para no degradar el rendimiento del sistema.
Simplificando a niveles prácticos el análisis de la complejidad espacial, básicamente podemos decir que se trata de determinar el tamaño del ejecutable, adicionado a cuánta memoria necesita cada elemento de una estructura, multiplicado por el máximo número de elementos, y ésto lo comparamos con la memoria disponible.

memoria libre <= tamaño_ejecutable + tamaño_elemento * máximo_elementos 

En cada estructura que estudiemos, haremos esta comparación, como un hábito que debe tener cada programador.

En el caso de la complejidad temporal, sí se requiere un análisis más detenido para llegar a una conclusión ¿cómo podemos analizar teóricamente el tiempo de ejecución sin ejecutar el algoritmo? ¿en qué computadora se realizará? dado que diferentes computadoras utilizan diferentes velocidades de ejecución ¿qué unidad de tiempo utilizar? ¿milisegundo o nanosegundos?

Para realizar el análisis de un algoritmo, independientemente de la computadora a usar, vamos a utilizar el siguiente principio:

Principio de la invarianza:   si dos implementaciones tardan respectivamente T1(n) y T2(n), entonces para resolver un problema con datos de tamaño n, existirá siempre una constante positiva c tal que T1(n) <= c * T2(n) para un n suficientemente grande

Ésto significa que T2(n) será c veces más rápido que T1(n), sin importar la computadora.  Si en una máquina T1(n)= 5 segundos y T2(n)= 1 segundo, en otra máquina más rápida T1(n)= 5 ms y T2(n)= 1 ms.  En otras palabras T2(n) siempre más rápido que T1(n), en cualquier máquina.

Por lo tanto no necesitamos una unidad de tiempo específica para comparación, ya que nuestro análisis es independiente de la máquina.  Usaremos una unidad de tiempo adimensional que denominaremos tiempo mìnimo denotado por t que es el tiempo en el que cualquier procesador ejecuta la instrucción más simple, como una asignación o expresión matemática.
Adicionalmente, la unidad de tiempo es irrelevante ya que la medida de eficiencia no es un número, sino una función:

Función de orden O(n) 
Se dice que f(n) es de orden g(n) si y sólo si

f(n) < = c * g(n)   para todo n > = n 0 
donde c y n0 son constantes positivas independientes de n

Ejemplo 1:

sea f(n) = 3n 3 + 2 n 2 
¿podemos decir que O(f(n) ) = n 3 ?  si tenemos c = 5 y n 0 = 0
= > se cumple que
          f(n) < = 5 * g(n) para todo n > = 0
= > 3n 3 + 2n 2 < = 5n 3 
= > 3n 3 + 2n 2 < = 3n 3 + 2n 3
=>                     2n 2 < =                   2n 3 
= >                       n 2 < =                   n 3 
para todo n > = 0

...