Capítulo 4,5,6 Analisis De Algoritmo

Capítulo 4: Análisis de Algoritmos

Metas del diseño de programas de cómputo:

• El diseño de un algoritmo que sea fácil de entender, codificar y depurar (Ingeniería de Software).

• El diseño de un algoritmo que haga uso eficiente de los recursos de la computadora (Análisis y Diseño de algoritmos).

El análisis de algoritmos nos permite medir la dificultad inherente de un problema y evaluar la eficiencia de un algoritmo.

Tiempo de ejecución

Esta función se puede medir físicamente (ejecutando el programa, reloj en mano), o calcularse sobre el código contando instrucciones a ejecutar y multiplicando por el tiempo requerido por cada instrucción.

Operaciones básicas o elementales para medir

Las operaciones básicas son las que realiza el computador en tiempo acotado por una constante, por ejemplo:

• Operaciones aritméticas básicas

• Asignaciones de tipos predefinidos

• Saltos (llamadas a funciones, procedimientos y retorno)

• Comparaciones lógicas

• Acceso a estructuras indexadas básicas (vectores y matrices)

Métodos para medir el tiempo de ejecución

Para medir el tiempo de ejecución de un algoritmo existen varios métodos. Veamos algunos de ellos:

a. Benchmarking

La técnica de benchmark considera una colección de entradas típicas representativas de una carga de trabajo para un programa.

b. Profiling

Consiste en asociar a cada instrucción de un programa un número que representa la fracción del tiempo total tomada para ejecutar esa instrucción particular.

c. Análisis

Consiste en agrupar las entradas de acuerdo a su tamaño, y estimar el tiempo de ejecución del programa en entradas de ese tamaño, T(n).

Complejidad

La complejidad (o costo) de un algoritmo es una medida de la cantidad de recursos (tiempo, memoria) que el algoritmo necesita. La complejidad de un algoritmo se expresa en función del tamaño (o talla) del problema.

Ordenes de complejidad

El orden de complejidad se expresa generalmente en términos de la cantidad de datos procesados por el programa, denominada n, que puede ser el tamaño dado o estimado.

Notación Asintótica

La notación asintótica se describe por medio de una función cuyo dominio es los números naturales (N) estimado a partir de tiempo de ejecución o de espacio de memoria de algoritmos en base a la longitud de la entrada. Se consideran las funciones asintóticamente no negativas.

La O mayúscula

La notación O se utiliza para comparar funciones. Resulta particularmente útil cuando se quiere analizar la complejidad de un algoritmo, en otras palabras, la cantidad de tiempo que le toma a un computador ejecutar un programa.

La o minúscula

Utilizaremos la notación o para denotar una cota superior que no es ajustada asintóticamente.

Diferencia entre O y o

Para o la desigualdad se mantiene para todas las constantes positivas, mientras que para O la desigualdad se mantiene sólo para algunas constantes positivas.

Las notaciones W y Q

W Es el reverso de O.

W Grande dice que asintóticamente f (x) domina a g (x).

Q Grande dice que ambas funciones se dominan mutuamente, en otras palabras, son asintóticamente equivalentes

Resolución de Recurrencias

Las ecuaciones de recurrencia son utilizadas para determinar cotas asintóticas en algoritmos que presentan recursividad.

Veremos dos técnicas básicas y una auxiliar que se aplican a diferentes clases de recurrencias:

• Método del teorema maestro

• Método de la ecuación característica

• Cambio de variable

Capítulo 5: Estrategias de Diseño de Algoritmos

Recursión

La recursividad es una técnica fundamental en el diseño de algoritmos eficientes, que está basada en la solución de versiones más pequeñas del problema, para obtener la solución general del mismo.

Ventajas de la recursividad:

• Puede resolver problemas complejos.

• Solución más natural.

Desventajas de la recursividad:

• Se puede llegar a un ciclo infinito.

• Versión no recursiva más difícil de desarrollar.

• Para la gente sin experiencia es difícil de programar.

Tipos de recursividad

• Directa o simple: un subprograma se llama a sí mismo una o más veces directamente

• Indirecta o mutua: un subprograma A llama a otro subprograma

...