Analisis De Algoritmos

INTRODUCCION:

La resolución práctica de un problema exige por una parte un algoritmo o método de resolución y por otra un programa o codificación de aquel en un ordenador real. Ambos componentes tienen su importancia; pero la del algoritmo es absolutamente esencial, mientras que la codificación puede muchas veces pasar a nivel de anécdota. A efectos prácticos o ingenieriles, nos debenpreocupar los recursos físicos necesarios para que un programa se ejecute. Aunque puede haber muchos parámetros, los más usuales son el tiempo de ejecución y la cantidad de memoria (espacio). Ocurre con frecuencia que ambos parámetros están fijados por otras razones y se plantea la pregunta inversa:

¿cual es el tamaño del mayor problema que puedo resolver en T segundos y/o con M bytes de memoria?
Enlo que sigue nos centraremos casi siempre en el parámetro tiempo de ejecución, si bien las ideas desarrolladas son fácilmente aplicables a otro tipo de recursos.

Estructura de Datos Unidad 7: Análisis de Algoritmos

7.1 COMPLEJIDAD EN EL TIEMPO

Cuando resolvemos un problema nos vemos frecuentemente enfrentando una elección de programas, es usual tener más de un programa para resolver unmisno problema, por ejemplo, ordenamiento. ¿En base a que elegimos? Usualmente hay dos objetivos contradictorios: 1.- Podemos querer un algoritmo fácil de entender, codificar y poner a punto. 2. - Podemos querer un algoritmo que haga un uso eficiente de los recursos de máquina (como ser tiempo y espacio), en particular uno que se ejecute lo más rápido posible. Cuando escribimos un programa queutilizaremos pocas veces, el objetivo 1) es más importante. Nos importa el tiempo que le lleva al programador codificar el programa luego el costo a optimizar es el costo de escribir el programa. Cuando nos enfrentamos a un problema cuya solución será utilizada muchas veces, el costo de ejecutar el programa es más importante que el costo de escribirlo. Luego vale la pena implementar un algoritmocomplicado dado que el programa resultante se ejecutara más rápido.

Estructura de Datos Unidad 7: Análisis de Algoritmos

Midiendo el tiempo de ejecución de un programa El tiempo de ejecución de un programa depende de factores tales como: 1. Tamaño o valor de la entrada al programa 2. Calidad del código generado por el compilador 3. Naturaleza y rapidez de las instrucciones en la máquina utilizadapara ejecutar el programa 4. Complejidad en el tiempo del algoritmo representado por el programa El hecho de que el tiempo de ejecución dependa de la entrada nos dice que el tiempo de ejecución de un programa debe definirse como una función de la entrada (o su tamaño). Un buen ejemplo es el de ordenamiento, en este caso tenemos como entrada una lista de elementos a ser ordenados y producimos comosalida los mismos elementos en orden. Por ejemplo dados 2; 1; 3; 1; 5; 8 como entrada produciremos 1; 1; 2; 3; 5; 8 como salida. La medida natural de la entrada en este caso es el largo de la entrada. En general consideraremos el tamaño de la entrada para medir la complejidad de los programas a menos que se diga lo contrario.

Estructura de Datos Unidad 7: Análisis de Algoritmos

Calculandoel tiempo de ejecución de un programa:

Regla de la suma
Supongamos que T1(n) y T2(n) son los tiempos de ejecución de dos fragmentos de programa P1 y P2. Supongamos T1 es O (f(n)) y T2 es O (g(n)). Luego el tiempo de ejecución de P1 seguido por P2 es O (max(f(n); g(n))). Veamos porque: Por hipótesis, hay constantes c1; c2; n1 y n2 tales que T1(n) · c1f(n) para n ¸ n1 y T2(n) · c2g(n) para n ¸n2. Consideremos n0 = max(n1; n2). Luego T1(n) + T2(n) ·

c1f(n) + c2g(n) para n ¸ n0 luego T1(n) + T2(n) · (c1 +c2)max(f(n); g(n)) para n ¸ n0 luegoT1(n) + T2(n) es O(max(f(n); g(n))).
En general, el tiempo de ejecución de una secuencia ¯ha de instrucciones es el tiempo de ejecución de la instrucción con mayor tiempo de ejecución. Listemos reglas generales para el análisis de programas. En...