Articulo completo aquiPrimera página
-------------------
Programación y Bases de Datos TEORIA
1 Eficiencia de los algoritmos
Motivación
En los primeros cursos de programación, se pretende que el estudiante sea capaz de escribir programas
cuidando aspectos como:
• La correción (que el programa cumpla la especificación),
• La legibilidad (que el programa sea fácil de entender),
• La concisión (que el programa no sea innecesariamente complejo).
En este apartado se estudia otro aspecto fundamental en el diseño de algoritmos: la eficiencia.
[Comparación de un algoritmo con el motor de un coche]
Es obvio que un objetivo natural al desarrollar programas es mantener el consumo de recursos lo más bajo
posible. Un algoritmo que resuelve un problema pero tarda un año en hacerlo, difícilmente será de
utilidad. Asímismo, un algoritmo que requiera varios gigabytes de memoria para resolver un problema no
es, actualmente, útil.
[Ejemplos: busquedores de Internet; planificador de rutas entre ciudades]
La eficiencia está determinada por la cantidad de recursos (tiempo y memoria, principalmente) que
consume un programa durante su ejecución. A menor consumo de recursos, mayor eficiencia.
La cantidad de recursos de un programa (es decir, su coste o complejidad) depende de gran cantidad de
factores, pero hay uno especialmente importante: el algoritmo en el que se basa el programa.
El conocer la eficiencia de un algoritmo nos permitirá:
• Estimar si un programa nos resolverá un problema usando un tiempo y memoria razonables.
• Dadas distintas formas de resolver un problema, escoger la más eficiente.
• Escribir algoritmos eficientes (junto con otras técnicas).
Contenido
1. Introducción. Qué es la eficiencia, de qué factores depende, cómo se expresa, cómo puede medirse.
2. Análisis de la complejidad algorítmica. Formas de analizar la eficiencia. Análisis del
comportamiento asintótico.
3. Notaciones asintóticas. Qué son las notaciones asintóticas. Propiedades. Formas de crecimiento.
4. Cálculo de la complejidad temporal. Cómo calcular la complejidad temporal asintótica de un
algoritmo.
5. Cálculo de la complejidad espacial. Cómo calcular la complejidad temporal asintótica de un
algoritmo.
6. Consideraciones. Cómo debe aplicarse todo lo referente a eficiencia. Cuándo debe usarse el coste
asintótico y cuándo no......
Articulo completo aqui