Análisis y Diseño de Algoritmos

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

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

1

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:
Tiempo de ejecución
Espacio en memoria

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

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

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

Principio de invarianza
Dos implementaciones de un mismo algoritmo no
diferirán másque en una constante multiplicativa.
Si t1(n) y t2(n) son los tiempos de dos
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 tamaño de las entradas.
T(n)

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

5

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

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

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

Análisis probabilístico
Asume unadistribución de probabilidad sobre las posibles entradas.

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

6

Eficiencia
Ejemplo
Algoritmo 1:

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

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ótico
7

Notacionesasintóticas

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

8

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

9

Notaciones asintóticas
Notación O
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) es O(f(n)) ⇔
∃c∈R, ∃n0∈N, tal que ∀n>n0∈N, T(n) ≤ cf(n)

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

11

Notaciones asintóticas
Notaciones Ω y ΘNotación Ω (cota inferior)
T(n) es Ω(f(n)) cuando
∃c∈R+, ∃n0∈N: ∀n≥n0 ⇒ T(n) ≥ cf(n)
cf(n)
Notación Θ (orden exacto)
T(n) es Θ(f(n)) cuando
T(n) es O(f(n)) y T(n) es Ω(f(n))
12

Órdenes de eficiencia
Órdenes de eficiencia más habituales
N

O(log2 n)

O(n2)

O(n log2 n)

O(n2)

O(2n)

O(n!)

10

3 µs

10 µs

30 µs

0.1 ms

1 ms

4s

25

5 µs

25 µs...