Jbajhad

CENTRO UNIVERSITARIO DE VALLADOLID
“FRANCISCO DE MONTEJO”


ALUMNO:
Cristian tejero

MATERIA:
Estructura De Datos
CARRRERA:
Lic. En Sistemas Computacionales
TEMA:
Complejidad
DOCENTE:
José Feliciano Hoil


VALLADOLID YUCATAN A 21 DE MAYO DE 2012

1. SELECCIÓN de un Algoritmo

La escogencia de un algoritmo para resolver un problema es un proceso en elque se deben tener en cuenta muchos factores, entre los cuales se pueden nombrar los siguientes:
La complejidad en tiempo del algoritmo. Es una primera medida de la calidad de una rutina, y establece su comportamiento cuando el número de datos que debe procesar es muy grande. Es importante tenerla en cuenta, pero no es el único factor que se debe considerar.
La complejidad en espacio delalgoritmo. Es una medida de la cantidad de espacio que necesita la rutina para representar la información. Sólo cuando esta complejidad resulta razonable es posible utilizar este algoritmo con seguridad. Si las necesidades de memoria crecen desmesuradamente con respecto al tamaño del problema, el rango de utilidad del algoritmo es bajo y se debe descartar.
La dificultad de implementar el algoritmo. Enalgunos casos el algoritmo óptimo puede resultar tan difícil de implementar, que no se justifique desarrollarlo para la aplicación que se le va a dar a la rutina. Si su uso es bajo o no es una operación crítica del programa que se está escribiendo, puede resultar mejor adoptar un algoritmo sencillo y fácil de implementar, aunque no sea el mejor de todos.
El tamaño del problema que se va a resolver.Si se debe trabajar sobre un problema de tamaño pequeño (v.g. procesar 20 datos), da prácticamente lo mismo cualquier rutina y cualquier estructura de datos para representar la información. No vale la pena complicarse demasiado y es conveniente seleccionar el algoritmo más fácil de implementar o el que menos recursos utilice.
El valor de la constante asociada con la función de complejidad. Si haydos algoritmos A1 y A2 de complejidad O( f( n ) ), el estudio de la función cota debe hacerse de una manera más profunda y precisa en ambos casos, para tratar de establecer la que tenga una menor constante. Las diferencias en tiempo de ejecución de dos rutinas con la misma complejidad pueden ser muy grandes, como se muestra en la figura 0.6. Además, este es un factor que se puede ajustar en laimplementación del algoritmo, lo cual hace que la calidad de la programación del algoritmo deba ser tenida en cuenta.

Fig. 0.6 - Funciones cota con diferentes constantes asociadas
El rango de tamaños del problema en el cual debe trabajar eficientemente el algoritmo. Para cierto número de datos, un algoritmo de complejidad O( n2 ) puede ser más eficiente que uno de complejidad O( n ), o inclusoque uno O( 1 ), como se sugiere en la figura 0.7. Por eso se debe determinar el rango de datos para el cual se espera que el algoritmo sea eficiente.

2. Tiempo de Ejecución
Una medida que suele ser útil conocer es el tiempo de ejecución de un programa en función de N, lo que denominaremos T(N). Esta función se puede medir físicamente (ejecutando el programa, reloj en mano), o calcularse sobreel código contando instrucciones a ejecutar y multiplicando por el tiempo requerido por cada instrucción. Así, un trozo sencillo de programa como
S1; for (int i= 0; i < N; i++) S2;
requiere
T(N)= t1 + t2*N
siendo t1 el tiempo que lleve ejecutar la serie "S1" de sentencias, y t2 el que lleve la serie "S2".
Prácticamente todos los programas realesincluyen alguna sentencia condicional, haciendo que las sentencias efectivamente ejecutadas dependan de los datos concretos que se le presenten. Esto hace que mas que un valor T(N) debamos hablar de un rango de valores
Tmin(N) <= T(N) <= Tmax(N)
los extremos son habitualmente conocidos como "caso peor" y "caso mejor". Entre ambos se hallara algun "caso promedio" o más...