matematica


Universidad Nacional Micaela Bastida de Apurímac

Departamento de Ingeniería





Escuela Académico Profesional de
Ingeniería Informática y Sistemas


MANUAL PARA EL ANÁLISIS DE LA COMPLEJIDAD DE LOS ALGORITMOS


Curso: Algorítmica III


Docente: Ing. Erech, Ordoñez Ramos






Abancay, diciembre del 2010.



Contenido






Introducción

Este Manualesta dirigido a todos los estudiantes de la Escuela Académico Profesional de Ingeniería Informática y Sistemas, quienes como parte de su formación profesional, hacen cálculos de la complejidad de los algoritmos y así saber su eficiencia, es decir el tiempo que tardará en ejecutarse y mejorar el mismo si es factible.

Por lo tanto el presente Manual nos ha de permitir medir de alguna forma el costo(en función del tiempo) que consume un algoritmo para encontrar la solución y nos permitirá la posibilidad de comparar distintos algoritmos que resuelven un mismo problema.


Objetivo del manual
Proporcionar al estudiante una guía que permita afianzar sus conocimientos relacionados al análisis de la complejidad de los algoritmos.

Eficiencia y complejidad
Una vez que dispongamos de unalgoritmo que funciona correctamente, es necesario definir criterios para medir su rendimiento o comportamiento. Estos criterios se centran principalmente en su simplicidad y en el uso eficiente de los recursos.
De ahí que muchas veces prime la simplicidad y legibilidad del código frente a alternativas más crípticas y eficientes del algoritmo.

Criterios para medir la eficiencia y complejidad deun algoritmo
Simplicidad
Uso eficiente de los recursos:
el espacio (memoria que utiliza)
y el tiempo (lo que tarda en ejecutarse).

Eficiencia temporal
Depender de diversos factores como son:
Los datos de entrada que le suministremos
La calidad del código generado por el compilador para crear el programa objeto
La naturaleza y rapidez de las instrucciones máquina del procesador concretoque ejecute el programa y
La complejidad intrínseca del algoritmo.

Existen dos estudios posibles sobre el tiempo:
1ro Medida teórica (a priori): Consiste en obtener una función que acote (por arriba o por abajo) el tiempo de ejecución del algoritmo para unos valores de entrada dados.
(Se vera en las clases teóricas)
2da Medida real (a posteriori): Consistente en medir el tiempo deejecución del algoritmo para unos valores de entrada dados y en un ordenador concreto.
(Se vera en la prácticas de laboratorio). Consiste en ejecutar casos de prueba, haciendo medidas para:
una máquina concreta,
un lenguaje concreto,
un compilador concreto y
datos concretos.

La unidad de tiempo a la que debe hacer referencia estas medidas de eficiencia se denotan por T(n) en donde n es el tamañode entrada.
T(n): Indica el número de instrucciones ejecutadas por un ordenador idealizado.

Por lo tanto un algoritmo tarda un tiempo de T(n).

Principio de Invarianza
Dado un algoritmo y dos implementaciones suyas I1 e I2, que tardan T1(n) y T2(n) segundos respectivamente, el Principio de Invarianza afirma que existe una constante real c > 0 y un número natural n0 tales que para todo nn0se verifica que T1(n)  cT2(n).



Con esto podemos definir sin problemas que un algoritmo tarda un tiempo del orden de T(n) si existen una constante real c > 0 y una implementación I del algoritmo que tarda menos que cT(n), para todo n como tamaño de entrada.

Dos factores a tener muy en cuenta son la constante multiplicativa y el n0 para los que se verifican las condiciones, pues si biena priori un algoritmo de orden cuadrático es mejor que uno de orden cúbico, en el caso de tener dos algoritmos cuyos tiempos de ejecución son 106n2 y 5n3 el primero sólo será mejor que el segundo para tamaños de la entrada superiores a 200.000.

El comportamiento de los algoritmos cambia notablemente para diferentes entradas, por lo cual se estudia tres casos para un mismo algoritmo:

Caso...