Diseño y analisis de algoritmos

1
Departamento de Lenguajes y Sistemas Informáticos
UNIVERSIDAD DE ALICANTE
TEMA 2
LA EFICIENCIA DE
LOS ALGORITMOS
2
La eficiencia de los algoritmos
OBJETIVOS
„ Proporcionar la capacidad para analizar con rigor la eficiencia
de los algoritmos
… Distinguir los conceptos de eficiencia en tiempo y en espacio
… Introducir las bases matemáticas para poder aplicar el criterioasintótico a los conceptos de eficiencia
… Calcular la complejidad temporal o espacial de un algoritmo
recursivo o iterativo
… Comparar, respecto a eficiencia, distintas soluciones algorítmicas
a un mismo problema2
3
La eficiencia de los algoritmos
CONTENIDO
1. Noción de complejidad
2. Cotas de complejidad
3. Análisis asintótico
4. Cálculo de complejidades
… Algoritmos Iterativos
…Algoritmos Recursivos. Ecuaciones de recurrencia
5. Anexo
4
1. Noción de complejidad
¿QUÉ ES UN ALGORITMO?
„ Un algoritmo es una serie finita de pasos que expresa una forma
o estrategia de resolución de un problema.
„ Importante:
… El número de pasos debe ser finito. El algoritmo debe terminar en
un tiempo finito.
… El algoritmo debe ser capaz de determinar la solución del
problema. Se tratade un método sistemático, susceptible de ser
realizado mecánicamente, para resolver un problema dado.3
5
1. Noción de complejidad
DEFINICIÓN
„ Complejidad de un algoritmo
… Medida de los recursos que un algoritmo necesita para su
ejecución
… Complejidad temporal: Tiempo que un algoritmo necesita para su
ejecución
… Complejidad espacial: Recursos espaciales (de almacén) que unalgoritmo consume o necesita para su ejecución
„ Posibilidad de hacer
… Valoraciones: el algoritmo A es “bueno”, “el mejor”, “prohibitivo”
… Comparaciones: el algoritmo A es mejor que el B
„ Nos centraremos en el estudio de la complejidad temporal
6
1. Noción de complejidad
COMPLEJIDAD TEMPORAL
„ El tiempo de ejecución de un algoritmo depende de:
… Factores externos
„ La máquina en la que seva a ejecutar
„ El compilador
„ La experiencia del programador
„ Los datos de entrada suministrados en cada ejecución
… Internos
„ El número de instrucciones asociadas al algoritmo
„ ¿Cómo estudiamos el tiempo de ejecución de un algoritmo?4
7
1. Noción de complejidad
¿CÓMO ESTUDIAMOS EL TIEMPO DE EJECUCIÓN?
„ Análisis empírico (a posteriori):
… Generando ejecuciones del algoritmo paradistintos valores de entrada y
cronometrando el tiempo de ejecución
J Se obtiene una medida real del comportamiento del algoritmo en el entorno de
aplicación
L El resultado depende de los factores externos e internos
„ Análisis analítico (a priori):
… Obtener una función que represente el tiempo de ejecución del algoritmo
para cualquier valor de entrada
J El resultado depende sólo de losfactores internos
J Estima el comportamiento del algoritmo de forma independiente de los
factores externos
J No es necesario implementar y ejecutar los algoritmos
L No obtiene una medida real del comportamiento del algoritmo en el entorno de
aplicación
„ Ambas medidas son importantes
8
1. Noción de complejidad
¿CÓMO ESTUDIAMOS EL TIEMPO DE EJECUCIÓN?
„ Se expresa mediante funciones decoste.
… Permiten determinar el comportamiento de un algoritmo para cualquier
entrada posible.
… Las entradas se expresan mediante lo que denominamos talla, tamaño
de la entrada o tamaño del problema.
„ Talla o tamaño de un problema:
… Valor o conjunto de valores asociados a la entrada del problema que
representa una medida de su tamaño respecto de otras entradas
posibles
„Denotaremos T(n) al tiempo de ejecución de un algoritmo para una
entrada de tamaño n.5
9
1. Noción de complejidad
¿CÓMO ESTUDIAMOS EL TIEMPO DE EJECUCIÓN?
„ ¿Qué unidad de medida empleamos para T(n)?
… ¿segundos? No existe unidad concreta
… No existe ordenador de referencia para estas medidas
„ El principio de Invarianza
… Dado un algoritmo y dos implementaciones I1 e I2 (máquinas o códigos...