PDF de programación - Tema 3.2: Eficiencia de algoritmos recursivos

Tema 3.2: Eficiencia de algoritmos recursivos

Diseño y Análisis de Algoritmos

Tema 3.2: Eficiencia de algoritmos recursivos

Contenidos

Contenidos

1

Introducción

2 Expansión de recurrencias

3 Método general para resolución de relaciones de recurrencia

URJC

DAA

2 / 37

Tema 3.2: Eficiencia de algoritmos recursivos

Introducción

Análisis de algoritmos recursivos

La matemática necesaria para analizar algoritmos recursivos son las
relaciones de recurrencia, también llamadas ecuaciones en
diferencias o simplemente recurrencias

Las recurrencias son expresiones matemáticas recursivas

3

T (n) =

5 + T (n − 1)

si n = 0
si n > 0

La resolución de recurrencias consiste en proporcionar fórmulas no
recursivas equivalentes

T (n) = 5n + 3

Veremos dos formas de resolverlas:

Expansión de recurrencias
Resolución de relaciones de recurrencia

URJC

DAA

3 / 37

Tema 3.2: Eficiencia de algoritmos recursivos

Expansión de recurrencias

Función potencia - versión 1

if(e==0)

1 int pot1(int b, int e)
2 {
3
4
5
6
7 }

return 1;

else

return b*pot1(b,e-1);

3

T (n) =

5 + T (n − 1)

si n = 0
si n > 0

n está relacionado con el tamaño del problema, que en este caso es el
exponente e de la función

Podemos pensar en el caso base se realizan 3 operaciones, y 5 en el
recursivo (además del tiempo que llevaría realizar otra llamada con
parámetro n − 1)

URJC

DAA

4 / 37

Tema 3.2: Eficiencia de algoritmos recursivos

Expansión de recurrencias

Resolución por expansión de recurrencias

T (n) = 5 + T (n − 1)

= 5 + 5 + T (n − 2) = 5 · 2 + T (n − 2)
= 5 + 5 + 5 + T (n − 3) = 5 · 3 + T (n − 3)
...
= 5i + T (n − i)

¿Cuándo se llega al caso base T (0)?

Cuando i = n

Sustituyendo:

T (n) = 5n + T (0) = 5n + 3 ∈ Θ(n)

Tiene sentido, ya que decrementamos n en cada llamada recursiva

URJC

DAA

5 / 37

Tema 3.2: Eficiencia de algoritmos recursivos

Expansión de recurrencias

Función potencia - versión 2

if(e==0)

return 1;

1 int pot2(int b, int e)
2 {
3
4
5
6
7
8
9 }

else if (e%2==0)

else

return pot2(b*b,e/2);

return b*pot2(b*b,e/2);

 3

T (n) =

8 + T (n/2)
9 + T ((n − 1)/2)

si n = 0
si n > 0 y n es par
si n > 0 y n es impar

La función es difícil de analizar
Pero podemos suponer que n = 2x es una potencia de dos
Esto es válido ya que estamos analizando complejidad asintótica

URJC

DAA

6 / 37

Tema 3.2: Eficiencia de algoritmos recursivos

Expansión de recurrencias

Resolución por expansión de recurrencias

Asumimos que n = 2x es una potencia de dos (por tanto, par):

T (n) = 8 + T (n/2)

= 8 + 8 + T (n/4) = 8 · 2 + T (n/22)
= 8 + 8 + 8 + T (n/8) = 8 · 3 + T (n/23)
...
= 8i + T (n/2i )

¿Cuándo se llega al caso base T (0)?

i → ∞
Pero eso no tiene sentido
El parámetro de la función T es entero

URJC

DAA

7 / 37

Tema 3.2: Eficiencia de algoritmos recursivos

Expansión de recurrencias

Resolución por expansión de recurrencias

¿Cuándo se llega al caso T (1)?

Cuando n/2i = 1, es decir, cuando i = log2 n

Sustituyendo:

T (n) = 8 log2 n + T (1) = 8 log2 n + 9 + T (0) = 8 log2 n + 9 + 3 =

= 8 log2 n + 12 ∈ Θ(log n)

Tiene sentido, ya que dividimos n por 2 en cada llamada recursiva

URJC

DAA

8 / 37

Tema 3.2: Eficiencia de algoritmos recursivos

Expansión de recurrencias

Soluciones generales a relaciones de recurrencia

a

T (n) =

b + T (n − 1)

si n = 0
si n > 0

T (n) = bn + a ∈ Θ(n)

a

T (n) =

b + T (n − 1)

si n = 1
si n > 1
T (n) = b(n − 1) + a ∈ Θ(n)

URJC

DAA

9 / 37

Tema 3.2: Eficiencia de algoritmos recursivos

Expansión de recurrencias

Soluciones generales a relaciones de recurrencia

a

T (n) =

si n = 1
si n > 1
T (n) = b log2 n + a ∈ Θ(log n)

b + T (n/2)

a

b + T (n/2)

T (n) =

si n = 0
si n > 0

T (n) = b log2 n + b + a ∈ Θ(log n)

URJC

DAA

10 / 37

Tema 3.2: Eficiencia de algoritmos recursivos

Expansión de recurrencias

Soluciones generales a relaciones de recurrencia

a

T (n) =

bn + c + T (n − 1)

si n = 0
si n > 0

T (n) = bn + c + T (n − 1)

= bn + c + b(n − 1) + c + T (n − 2) = 2bn − b + 2c + T (n − 2)
= 2bn − b + 2c + b(n − 2) + c + T (n − 3) =
= 3bn − b(1 + 2) + 3c + T (n − 3) =
= 3bn − b(1 + 2) + 3c + b(n − 3) + c + T (n − 4) =
= 4bn − b(1 + 2 + 3) + 4c + T (n − 4) =
...
= ibn − b

j + ic + T (n − i) = ibn + ic − b

i(i − 1)

+ T (n − i)

2

i−1

j=1

URJC

DAA

11 / 37

Tema 3.2: Eficiencia de algoritmos recursivos

Expansión de recurrencias

Soluciones generales a relaciones de recurrencia

Se alcanza T (0) para i = n

Sustituyendo:

T (n) = bn2 − b
2

n(n − 1) + cn + a



T (n) =

b
2

n2 +

c +

b
2

n + a ∈ Θ(n2)

Tiene sentido, ya que hacemos n + (n − 1) + (n − 2) + ··· + 1
operaciones

URJC

DAA

12 / 37

Tema 3.2: Eficiencia de algoritmos recursivos

Expansión de recurrencias

Soluciones generales a relaciones de recurrencia

T (n) =

bn + c + 2T (n/2)

si n = 0
si n > 0

a



n
2

n
2

T (n) = bn + c + 2T (n/2)

= bn + c + 2

= bn + c + 2



b

+ c + 2T (n/4)



b

+ c + 2

b

n
4

+ c + 2T (n/8)

= 3bn + c(1 + 2 + 4) + 23T (n/23) = 3bn + c(23 − 1) + 23T (n/23)
...
= ibn + c(2i − 1) + 2i T (n/2i )

URJC

DAA

13 / 37

Tema 3.2: Eficiencia de algoritmos recursivos

Expansión de recurrencias

Soluciones generales a relaciones de recurrencia

Se alcanza T (1) para n/2i = 1, es decir, cuando i = log2 n

Sustituyendo:

T (n) = bn log2 n + c(n − 1) + nT (1)

= bn log2 n + c(n − 1) + n(b + c + 2T (0))

= bn log2 n + cn − c + nb + nc + 2na

T (n) = bn log2 n + (2c + b + 2a)n − c

∈ Θ(n log n)

URJC

DAA

14 / 37

Tema 3.2: Eficiencia de algoritmos recursivos

Expansión de recurrencias

Soluciones generales a relaciones de recurrencia

Tiene sentido, ya que hacemos n operaciones 1 + log2 n veces

URJC

DAA

15 / 37

nn/2n/2n/4n/4n/4n/41111111111111111n1 + log2 n Tema 3.2: Eficiencia de algoritmos recursivos

Expansión de recurrencias

Teorema maestro - versión simple

Fórmula útil para algoritmos “divide y vencerás”:

 c

T (n) =

aT (n/b) + cnk

si n = 1

si n > 1

=⇒

T (n) =



Θ(nk )

Θ(nk log n)

Θ(nlogb a)

si a

bk < 1

si a

bk = 1

si a

bk > 1

URJC

DAA

16 / 37

Tema 3.2: Eficiencia de algoritmos recursivos

Expansión de recurrencias

Teorema maestro - demostración

T (n) = aT (n/b) + cnk

= a

aT

+ c



b2


n
n


n

aT

b3

bi

= a2

...

= ai T

+ cnk = a2T

b

k
n
k
+ cnk n
n
a
j
i−1

b2

b2



n


b2

+ cnk
n


b3



1 +

a
bk



a
bk +

a2
b2k

+ c

= a3T

+ cnk

1 +

+ cnk

bk

j=0

Se alcanza T (1) = c cuando: i = logb n

= calogb n + cnk

logb n−1

a

j

bk

j=0

= cnk a

bk

logb n

logb n−1

a

j

bk

j=0

+ cnk

URJC

DAA

17 / 37

Tema 3.2: Eficiencia de algoritmos recursivos

Expansión de recurrencias

Teorema maestro - demostración (logaritmos)

La última igualdad se debe a:

logb n

cnk a

bk

= cnk alogb n

bk logb n = cnk alogb n

nk = calogb n

Más adelante también necesitaremos:

nlogba = alogbn

Ya que:

logb nlogba = logb alogbn = logb a · logb n

Finalmente:

logb n

a

j

bk

j=0

T (n) = cnk

Y tendremos 3 casos según los valores de a, b y k

URJC

DAA

18 / 37

Tema 3.2: Eficiencia de algoritmos recursivos

Expansión de recurrencias

Teorema maestro - demostración

logb n

j=0

T (n) = cnk

a

j

bk

1 a < bk ⇒ T (n) ∈ Θ(nk )

∞

i=0

r i =

1
1 − r

= constante (no diverge), para r < 1

2 a = bk ⇒ T (n) ∈ Θ(nk log n)

T (n) = cnk (logb n + 1)

URJC

DAA

19 / 37

Tema 3.2: Eficiencia de algoritmos recursivos

Expansión de recurrencias

Teorema maestro - demostración

logb n

a

j

bk

j=0

T (n) = cnk

3 a > bk ⇒ T (n) ∈ Θ(nlogb a)

a

bk

logb n+1 − 1
− 1
a

bk

cnk a

alogb n
nk − cnk
K1
K2nlogb a − cnk

bk

=

T (n) = cnk

K2alogb n − cnk

=

K1
Como a > bk ⇒ logb a > k ⇒ T (n) ∈ Θ(nlogb a)

K1

=

URJC

DAA

20 / 37

Tema 3.2: Eficiencia de algoritmos recursivos

Expansión de recurrencias

Teorema maestro - versión completa

Dada una recurrencia del tipo:

T (n) = aT (n/b) + f (n)

donde a > 0, b > 0, y f (n) es una función asintóticamente positiva,
entonces se puede aplicar el teorema maestro en estos tres casos:

URJC

DAA

21 / 37

Tema 3.2: Eficiencia de algoritmos recursivos

Expansión de recurrencias

Teorema maestro - versión completa

1 Si f (n) = O(nlogba−
) para alguna constante
> 0, entonces:

T (n) ∈ Θ(nlogba)

2 Si f (n) = Θ(nlogbalog k n) con1 k ≥ 0, entonces:
T (n) ∈ Θ(nlogbalog k+1n)

3 Si f (n) = Ω(nlogba+
) con
> 0, y f (n) satisface la condición de
regularidad (af (n/b) ≤ cf (n) para alguna constante c < 1 y para
todo n lo suficientemente grande), entonces:
T (n) ∈ Θ(f (n))

1k suele ser 0

URJC

DAA

22 / 37

Tema 3.2: Eficiencia de algoritmos recursivos Método general para resolución de relaciones de recurrencia

Método general para resolución de relaciones de
recurrencia

No siempre se puede aplicar la expansión de recurrencias

Para muchas recurrencias no se conoce la forma de resolverlas

Sucede como con las integrales o ecuaciones diferenciales: sabemos
como resolver un subconjunto de éstas, pero no todas

Ahora veremos un método general con el que vamos a ampliar el
conjunto de recurrencias que podemos resolver

URJC

DAA

23 / 37

Expansión derecurrenciasMétodo generalde resolución de recurrenciasRecurrencias Tema 3.2: Eficiencia de algoritmos recursivos Método general para resolución de relaciones de recurrencia

Recurrencias homogéneas

Dada la siguiente recurrencia homogénea (aparece un 0 en la parte
derecha):

a0T (n) + a1T (