Eficiencia de los Algoritmos

La
La eficiencia de los algoritmos
Análisis y Diseño de Algoritmos

La eficiencia de los algoritmos
Comparación
Comparación de algoritmos
Principio
Principio de invarianza
Eficiencia
Eficiencia
Notaciones
Notaciones asintóticas
Cálculo
Cálculo de la eficiencia de un algoritmo
Resolución
Resolución de recurrencias:
Método de la ecuación característica
Recurrencias
Recurrenciashomogéneas
Recurrencias
Recurrencias no homogéneas
Cambios
Cambios de variable
Transformaciones
Transformaciones del rango
Apéndice:
Apéndice: Fórmulas útiles

1

Comparación
Comparación de algoritmos
A menudo dispondremos de más de un algoritmo para
resolver un problema dado, ¿con cuál nos quedamos?
USO DE RECURSOS
Computacionales:
Computacionales:
Tiempo
Tiempo de ejecuciónEspacio
Espacio en memoria

No
No computacionales:
Esfuerzo
Esfuerzo de desarrollo (análisis, diseño & implementación)
2

Comparación de algoritmos
Factores que influyen en el uso de recursos
Recursos
Recursos computacionales:
Diseño
Diseño del algoritmo
Complejidad
Complejidad del problema (p.ej. tamaño de las entradas)
Hardware
Hardware (arquitectura, MHz, MBs…)
CalidadCalidad del código
Calidad
Calidad del compilador (optimizaciones)

Recursos
Recursos no computacionales:
Complejidad
Complejidad del algoritmo
Disponibilidad
Disponibilidad de bibliotecas reutilizables
3

Principio
Principio de invarianza
Dos
Dos implementaciones de un mismo algoritmo no
diferirán más que en una constante multiplicativa.
Si
Si t1(n) y t2(n) son los tiempos de dosimplementaciones
implementaciones de un mismo algoritmo,
se puede comprobar que:

∃c, d ∈ ℜ, t1 (n) ≤ ct2 (n); t 2 (n) ≤ dt1 (n)

4

Eficiencia

Medida del uso de los recursos computacionales
requeridos por la ejecución de un algoritmo en función
del
del tamaño de las entradas.
T(n)

Tiempo empleado para ejecutar el
algoritmo con una entrada de tamaño n

5

EficienciaEficiencia
Tipos de análisis
¿Cómo medimos el tiempo de ejecución de un algoritmo?
Mejor
Mejor caso
En
En condiciones óptimas (no se usa por ser demasiado optimista).

Peor
Peor caso
En el peor escenario posible (nos permite acotar el tiempo de ejecución).

Caso
Caso promedio
Caso difícil de caracterizar en la práctica.

Análisis
Análisis probabilístico
Asume una distribución deprobabilidad sobre las posibles entradas.

Análisis
Análisis amortizado
Tiempo medio de ejecución por operación
sobre una secuencia de ejecuciones sucesivas.

6

Eficiencia
Ejemplo
Algoritmo
Algoritmo 1:

T(n) = 10-4 2n segundos
n = 38 datos
T(n) = 1 año

Algoritmo
Algoritmo 2:

T(n) = 10-2 n3 segundos
n = 1000 bits
T(n) = 1 año

¿Cuál es mejor? Se precisa un análisis asintóticoanálisis
7

Notaciones
Notaciones asintóticas

Estudian el comportamiento del algoritmo cuando el
tamaño de las entradas es lo suficientemente grande,
sin
sin tener en cuenta lo que ocurre para entradas
pequeñas
pequeñas y obviando factores constantes.

8

Notaciones asintóticas
Orden de eficiencia
orden
Un algoritmo tiene un tiempo de ejecución de orden
f(n), para una funcióndada f, si existe una constante
positiva
positiva c y una implementación del algoritmo capaz
de
de resolver cada caso del problema en un tiempo
tiempo
acotado superiormente por c·f (n), donde n es el
c·f (n)
tamaño del problema considerado.

9

Notaciones
Notaciones asintóticas
Notación O
T(n)
Decimos que una función T(n) es O(f(n))
si existen constantes n0 y c
tales que T(n) ≤cf(n) para todo n ≥ n0:
T(n)
T(n) es O(f(n)) ⇔
∃c∈R, ∃n0∈N, tal que ∀n>n0∈N, T(n) ≤ cf(n)

10

Notaciones asintóticas
Ejemplos
T(n) = 3n
T(n)
T(n) es O(n), O(n log n), O(n2), O(n3) y O(2n).
T(n) = (n+1)2
T(n) es
T(n) es O(n2), O(n3) y O(2n).
T(n)
T(n) no es O(n) ni O(n log n).
T(n) = 32n2 + 17n + 32(n) = 32n2 + 17n + 32.
T(n)
T(n) es O(n2) pero no es O(n).
T(n) = 3n3 + 345n2...