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:




No


Tiempo de ejecución Espacio en memoria

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

Comparación de algoritmos Factores que influyen en el uso de recursos
Recursos






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



computacionales:

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 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 el algoritmo 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 una distribució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

Notaciones asintó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),, para una función dada f, si existe una constante f(n) positiva c y una implementación del algoritmo capaz de resolver cada caso del problema en un tiempo acotado superiormente por c·f (n) (n),, donde n es el 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 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) (n) = 32n2 + 17n + 32.
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

0.1 ms

0.6 ms

33 s

1011 años

50

6 µs

50 µs

0.3 ms

2.5 ms

36 años

…

100

7 µs

100 µs

0.7 ms

10 ms

1017 años

…

1000

10 µs

1 ms

10 ms

1s

…

…

10000

13 µs

10 ms

0.1 s

100 s

…

…

100000

17 µs

100 ms

1.7 s

3 horas

…

…

1000000

20 µs

1s

20 s

12 días

…

…

Tiempos calculados suponiendo 1 µs por operación elemental. O(1) ⊂ O(log n) ⊂ O(n) ⊂ O(n log n) ⊂ O(n2) ⊂ O(n3) ⊂ O(2n) ⊂ O(n!)

13

Órdenes de eficiencia Orden lineal: O(n) Tiempo de ejecución proporcional al tamaño de la entrada.

Ejemplo: Calcular el máximo de n números a1, …, an. max ← a1 for i = 2 to n { if (ai > max) max ← ai }

14

Órdenes de eficiencia Orden cuadrático: O(n2) Aparece cuando tenemos que enumerar todas las parejas posibles de elementos de un conjunto. Ejemplo: Dado un conjunto de puntos en el plano (x1, y1), …, (xn, yn), encontrar la pareja más cercana. min ← (x1 - x2)2 + (y1 - y2)2 for i = 1 to n { for j = i+1 to n { d ← (xi - xj)2 + (yi - yj)2 if (d < min) min ← d } } 15

Órdenes de eficiencia Órdenes O(log n) y O(n log n) Aparecen en muchos algoritmos recursivos p.ej. Estrategia “divide y vencerás” Ejemplos:

O(log n) O(n log n)

Búsqueda binaria Mergesort,, Heapsort… Mergesort Heapsort…

Orden exponencial O(2n) Aparece en muchos problemas de tipo combinatorio Ejemplo: Enumerar todos los subconjuntos de un conjunto dado. 16

Cálculo de la eficiencia Operación elemental Operación de un algoritmo cuyo tiempo de ejecución se puede acotar superiormente por una constante.


En nuestro análisis, sólo contará el número de operaciones elementales y no el tiempo exacto necesario para cada una de ellas.




En la descripción de un algoritmo, puede ocurrir que una línea de código corresponda a un número de variable de operaciones elementales. p.ej.

x ← max max{A[k], {A[k], 0 1 ¿T(n) es O(n3)? Suponemos que T(k) ≤ ck3 para k0 (p.ej. c≥2 y n≥1) PROBLEMA: ¿Podríamos encontrar una cota superior más ajustada? Sugerencia: Probar con T(n) ≤ cn2 y T(n) ≤ c1n2-c2n

34

Árbol de recursividad T (n ) = T ( n / 4) + T ( n / 2) + n 2

35

Ecuación característica Recurrencias homogéneas lineales con coeficientes constantes

a0tn + a1tn −1 + L + ak tn −k = 0




Lineal: No hay términos tn-1tn-j, t2n-i Homogénea: Igualadas a 0 Con coeficientes constantes: ai constantes

Ejemplo: Sucesión de Fibonacci

f n = f n −1 + f n − 2

⇒

f n − f n −1 − f n − 2 = 0 36

Ecuación característica Suposición: tn = xn

a0 x n + a1 x n −1 + L + ak x n −k = 0 Se satisface si x=0 o bien

a0 x k + a1 x k −1 + L + ak = 0 ecuación característica Polinomio característico

p( x ) = a0 x k + a1 x k −1 + L + ak 37

Ecuación característica Teorema Fundamental del Álgebra:

k

p( x ) =∏ ( x − ri ) i =1

Consideremos una raíz del polinomio característico, ri

p( p(rri) = 0 Por tanto, rin es solución de la recurrencia. Además, las combinaciones lineales de las soluciones de la recurrencia también son soluciones: k

tn = ∑ ci ri n i =1

Cuando todos los ri son distintos distintos,, éstas son las únicas soluciones

38

Ecuación característica Resolución de recurrencias mediante el método de la ecuación característica: 1.

2. 3.

4.

Se obtiene la ecuación característica asociada a la recurrencia que describe el tiempo de ejecución T(n). Se calculan las k raíces del polinomio característico. Se obtiene la solución a partir de las raíces del polinomio característico. Se determinan las constantes a partir de las k condiciones iniciales. 39

Ecuación característica Ejemplo: Sucesión de Fibonacci

n,  fn =   f n −1 + f n −2

si n = 0 ó n = 1 en otro caso

f n − f n −1 − f n −2 = 0

p( x ) = x 2 − x − 1

r1 =

1+ 5 2

y

r2 =

1− 5 2

40

Ecuación característica Ejemplo: Sucesión de Fibonacci

f n = c1r1n + c2 r2n c1

+

c2

r1c1 + r2c2

= 0  ⇒ = 1

c1 =

1 5

y c2 = −

1 5

n n  1 1+ 5  1− 5      −  fn =    5  2   2     41

Ecuación característica Ejemplo:

0, n=0   tn =  5, n =1 3t + 4t , en otro caso n −2  n −1

tn − 3tn −1 − 4tn −2 = 0

x 2 − 3x − 4 = ( x + 1)( x − 4)

tn = c1 ( −1) n + c2 4n A partir de las condiciones iniciales: c1 = -1, c2 = 1 42

Ecuación característica Raíces múltiples Supongamos que las raíces del polinomio característico NO son todas distintas. ri con multiplicidad mi l

mi −1

tn = ∑ ∑ cij n j ri n i =1 j = 0

43

Ecuación característica Ejemplo:

n, si n = 0, 1 ó 2  tn =  5tn −1 − 8tn −2 + 4tn −3 en otro caso

tn − 5tn −1 + 8tn −2 − 4tn −3 = 0 x 3 − 5 x 2 + 8 x − 4 = ( x − 1)( x − 2)2

tn = c1 (1)n + c2 2n + c3n 2n A partir de las condiciones iniciales: c1 = -2, c2 = 2, c3 = -1/2

tn = 2n +1 − n 2n −1 − 2

44

Ecuación característica Recurrencias no homogéneas A partir de

a0t n + a1t n −1 + L + ak t n − k = b n p (n)

donde b es una constante y p(n) un polinomio de grado d derivamos el polinomio característico

p ( x ) = ( a0 x k + a1 x k −1 + L + ak )( x − b) d +1 que resolveremos igual que en el caso homogéneo. 45

Ecuación característica Ejemplo: Las torres de Hanoi

hanoi (int n, int inicial, int final, int tmp tmp) ) { hanoi (n – 1, inicial, tmp tmp, , final) final  inicial hanoi (n – 1, tmp tmp, , final, inicial) }

0, n =0  T (n) =  2T (n − 1) + 1, en otro caso

46

Ecuación característica Ejemplo: Las torres de Hanoi

t n − 2t n −1 = 1

p ( x) = ( x − 2)( x − 1) T (n) = c1 2 n + c2

t n = c1 2 n + c21n T ( 0) = 0  ⇒ T (1) = 1 

c1

+ c2

2c1

+ c2

c1 = 1 = 0 ⇒  c2 = −1 = 1

T ( n) = 2 n − 1

47

Ecuación característica Ejemplo:

tn = 2tn −1 + n;

t0 = 0

p( x ) = ( x − 2)( x − 1) 2 t n = c1 2 n + c21n + c3n1n c1 + c2 2c1 + c2

+ c3

4c1 + c2

+ 2c3

= 0 c1 = 2  = 1  ⇒ c2 = −2 = 4  c3 = −1

tn = 2n +1 − n − 2

48

Ecuación característica Recurrencias no homogéneas

a0t n + a1t n −1 + L + ak t n − k = b1n p1 (n) + ... + bsn ps (n)



b1, …, bs constantes pi(n) polinomio de grado di

Polinomio característico:

p ( x ) = ( a0 x k + a1 x k −1 + L + ak )( x − b1 ) d1 +1 L ( x − bs ) d s +1 49

Ecuación característica Cambios de variable Cuando las recurrencias no se ajustan al tipo conocido…

1, n =1  T (n) = 3T (n / 2) + n, n > 1 aplicamos un cambio de variable n = 2i que nos permite definir una nueva recurrencia:

ti = T (2i ) 50

Ecuación característica Cambios de variable

ti = 3ti −1 + 2i

⇒

ti = c1 3i + c2 2i

Finalmente, deshacemos el cambio de variable: i = log2(n)

T ( n ) = c1 3log2 ( n ) + c2 2log2 ( n ) = c1n log2 ( 3) + c2n

T (n) es O(n log 2 (3) ) 51

Ecuación característica Ejemplo

ti = T (2i )

1, n =1  T ( n) = 4T ( n / 2) + n, n > 1

ti = 4ti −1 + 2i

⇒

ti = c1 4i + c2 2i

T (n) = c1 4 log 2 ( n ) + c2 2 log 2 ( n ) = c1n log 2 ( 4 ) + c2 n = c1n 2 + c2 n

T (n) es O(n 2 ) 52

Ecuación característica Ejemplo

ti = T (2i )

1, n =1  T ( n) = 2T ( n / 2) + n, n > 1

ti = 2ti −1 + 2i

⇒

ti = c1 2i + c2i 2i

T (n) = c1 2 log 2 ( n ) + c2 log 2 (n)2log 2 ( n ) = c1n + c2 n log 2 (n)

T (n) es O(n log 2 n) 53

Ecuación característica Recurrencia “divide y vencerás” a.k.a. “the master method method””

n T ( n ) = aT   + cn k b

con a ≥ 1, b ≥ 2, k ≥ 0, c > 0

 Θ( n k ), a < bk  T ( n ) = Θ( n k logb ( n )), a = bk k  Θ( n logb ( a ) ) > a b  54

Ecuación característica Transformaciones del rango

n =1  1 / 3,  T ( n) =  2  n  nT  , en otro caso  2 Inicialmente, realizamos un cambio de variable:

ti = T (2i ) = 2i T 2 (2i −1 ) = 2i ti2−1 Como esta recurrencia no es lineal y el coeficiente 2i no es constante, tomamos logaritmos:

ui = log(ti ) = i + 2 log(ti −1 ) = i + 2ui −1

55

Ecuación característica Transformaciones del rango

ui = i + 2ui −1 ui − 2ui −1 = i ui = c1 2i + c21i + c3i1i Sustituyendo en la recurrencia para ui, obtenemos:

i = ui − 2ui −1 = c1 2i + c2 + c3i − 2(c1 2i −1 + c2 + c3 (i − 1)) i = (2 − i )c3 − c2 (1 + c3 )i = 2c3 − c2

c3 = −1; c2 = −2 56

Ecuación característica Transformaciones del rango

ui = c1 2i − i − 2 Deshacemos los cambios:

ti = 2 = 2 ui

c1 2i −i − 2

T (n) = tlog 2 ( n ) = 2

c1n − log 2 n − 2

2 c1n = 4n

A partir de las condiciones iniciales:

T (1) = 2 c1 / 4 = 1 / 3 ⇒ c1 = log 2 (4 / 3) = 2 − log 2 3 2c1n 2 ( 2−log 2 3) n 22n 22n T ( n) = = = = 4n 4n 4n 2 (log 2 3) n 4n3n

57

Apéndice: Fórmulas útiles Progresiones aritméticas

ai +1 = ai + d n

1 ai = n (a1 + an ) ∑ 2 i =1 n

∑i = i =1

1 n (n + 1) 2

58

Apéndice: Fórmulas útiles Progresiones geométricas

ai +1 = r ai a1 (r n +1 − 1) ai = ∑ r −1 i =1 n

n +1 b −b i b = ∑ b −1 i =1 n

59

Apéndice: Fórmulas útiles Sumatorias n

∑ a = na i =1

n

n

i =1

i =1

∑ a f (i) = a∑ f (i)

∑ (a + b ) = ∑ a + ∑ b ∑∑ a b = ∑ a ∑ b i

i

j

j

i

i

j

j

60

Apéndice: Fórmulas útiles Sumatorias n

1 n (n + 1) 2 i =1 n 1 2 i = n (n + 1)(2n + 1) ∑ 6 i =1 2 n 1   i 3 =  n (n + 1) ∑ 2  i =1 n 1 i i + = n (n + 1)(n + 2) ( 1 ) ∑ 3 i =1

∑i =

61

Apéndice: Fórmulas útiles Potencias

x y + z = x y ·x z x y−z = x y / x z

x y ·z = ( x y ) z = ( x z ) y x

yz

≠x

z

y

¡Ojo!

62

Apéndice: Fórmulas útiles Logaritmos

log a (n) =

log b (n) log b (a )

log a (n m) = log a (n ) + log a (m) log a ( n / m) = log a ( n ) − log a (m)

log a (n p ) = p log a (n )

n loga ( m ) = m loga ( n ) 63