Tecnico en Computacion

Análisis Algorítmico
La eficiencia de un programa tiene dos ingredientes fundamentales: espacio y tiempo. La eficiencia en espacio es la cantidad de memoria requerida por un programa. La eficienciaen tiempo la cantidad de tiempo de ejecución del programa. Ambas dependen del tipo de computador y compilador, por lo que no se estudiará aquí la eficiencia de los programas, sino la eficiencia delos algoritmos. Centraremos nuestra atención en los algoritmos para máquinas de un solo procesador que ejecutan una instrucción luego de otra.
La eficiencia de los algoritmos está basada en unaoperación característica que el algoritmo repite y que define su complejidad en Tiempo (T(n)).
T(n) es el número de operaciones características que el algoritmo desarrolla para una entrada N dada.
El máximotiempo de ejecución de un algoritmo para todas las instancias de tamaño N, se denomina la complejidad en tiempo para el peor caso W(n). Asimismo, la complejidad promedio en tiempo es A(n), donde pjes la probabilidad de que esta instancia ocurra.
Normalmente se tendrán muchos algoritmos diferentes para resolver un mismo problema, por lo que debe existir un criterio para seleccionar el mejor. Elinterés principal del análisis de algoritmos radica en saber cómo crece el tiempo de ejecución, cuando el tamaño de la entrada crece. Esto es la eficiencia asintótica del algoritmo. La notaciónasintótica se describe por medio de una función cuyo dominio es los números naturales (N). Se consideran las funciones asintóticamente no negativas.
Orden de un algoritmo
La mejor técnica para diferenciarla eficiencia de los algoritmos es el estudio de los órdenes de complejidad. El orden de complejidad se expresa generalmente en términos de la cantidad de datos procesados por el programa, denominadan, que puede ser el tamaño dado o estimado.
Ejemplo: Un algoritmo que procese un vector V(n) tendrá un orden de complejidad de n, ya que si n crece, en esa misma proporción crece el orden de...