Algoritmos recursivos

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 rango Apé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 recursos Recursoscomputacionales:
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ás que en una constantemultiplicativa. 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 el algoritmo con una entrada de tamaño n5

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 una distribución de probabilidad sobre lasposibles 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 T(n) = 10-2 n3 segundos n = 1000 bits T(n) = 1 año

Algoritmo 2:

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

Notaciones asintóticas

Estudian el comportamiento delalgoritmo 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 una implementación del algoritmo capaz de resolver cada caso delproblema 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)

10

Notaciones asintóticas
Ejemplos T(n) = 3n T(n) es O(n), O(n logn), 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 10 25 50 100 1000 10000 100000 1000000 O(log2 n) 3 µs 5 µs 6 µs 7 µs 10 µs 13 µs 17 µs 20 µs O(n2) 10 µs 25 µs 50 µs 100 µs 1 ms 10 ms 100 ms 1s O(n log2 n) 30 µs 0.1 ms 0.3 ms 0.7 ms 10 ms 0.1 s 1.7 s 20 s O(n2) 0.1 ms 0.6 ms 2.5...