PDF de programación - Algoritmos recursivos - Análisis de algoritmos

Análisis de algoritmos
Algoritmos recursivos

Dra. Elisa Schaeffer

[email protected]

PISIS / FIME / UANL

Algoritmos recursivos– p. 1

Algoritmos simples

Para analizar desde un pseudocódigo la complejidad,
típicamente se aplica las reglas siguientes:

Asignación de variables simples toman tiempo O (1).
Escribir una salida simple toma tiempo O (1).
Leer una entrada simple toma tiempo O (1).

Algoritmos recursivos– p. 2

Sucesiones y condiciones

Si las complejidades de una sucesión de instrucciones
I1, I2, . . . , Ik son respectivamente f1, f2, . . . , fk, la
complejidad total de la sucesión es

O (f1 + f2 + . . . + fk) = O (máx{f1, . . . , fk})
siempre y cuando k no depende del tanaño de la
instancia.

Algoritmos recursivos– p. 3

Sucesiones y condiciones

Si las complejidades de una sucesión de instrucciones
I1, I2, . . . , Ik son respectivamente f1, f2, . . . , fk, la
complejidad total de la sucesión es

O (f1 + f2 + . . . + fk) = O (máx{f1, . . . , fk})
siempre y cuando k no depende del tanaño de la
instancia.
La complejidad de una cláusula de condición (si ) es la
suma del tiempo de evaluar la condición y la
complejidad de la alternativa ejecutada.

Algoritmos recursivos– p. 3

Bucles, llamadas y arreglos

La complejidad de una repetición
(mientras , para , . . .) es O (k(ft + fo)), donde k es el
número de veces que se repite, ft es la complejidad
de evaluar la condición de terminar y fo la complejidad
de la sucesión de operaciones de las cuales consiste
una repetición.

Algoritmos recursivos– p. 4

Bucles, llamadas y arreglos

La complejidad de una repetición
(mientras , para , . . .) es O (k(ft + fo)), donde k es el
número de veces que se repite, ft es la complejidad
de evaluar la condición de terminar y fo la complejidad
de la sucesión de operaciones de las cuales consiste
una repetición.
La complejidad de tiempo de una llamada de
subrutina es la suma del tiempo de calcular sus
parámetros, el tiempo de asignación de los parámetros
y el tiempo de ejecución de las instrucciónes.

Algoritmos recursivos– p. 4

Bucles, llamadas y arreglos

La complejidad de una repetición
(mientras , para , . . .) es O (k(ft + fo)), donde k es el
número de veces que se repite, ft es la complejidad
de evaluar la condición de terminar y fo la complejidad
de la sucesión de operaciones de las cuales consiste
una repetición.
La complejidad de tiempo de una llamada de
subrutina es la suma del tiempo de calcular sus
parámetros, el tiempo de asignación de los parámetros
y el tiempo de ejecución de las instrucciónes.

Operaciones aritméticas y asignaciones que procesan
arreglos o conjuntos tienen complejidad lineal en el
tamaño del arreglo o conjunto.

Algoritmos recursivos– p. 4

Algoritmos recursivos

La complejidad de programas recursivos típicamente
involucra la solución de una ecuación diferencial.
El método más simple es adivinar una solución y
verificar si está bien la adivinanza.

Algoritmos recursivos– p. 5

T (n) ≤( c,

gT (n/2), n,

Adivinamos que la solución sea, en forma general,
T (n) ≤ f (a1, . . . , aj, n), donde a1, . . . , aj son parámetros de
la función f.

Ejemplo

si n = 1
si n > 1

Algoritmos recursivos– p. 6

La meta

Para mostrar que para algunos valores de los parámetros
a1, . . . , aj aplica ∀n que la solución sea la adivinada,
tenemos que demostrar que

y también que

c ≤ f (a1, . . . , aj, 1)

gfa1, . . . , aj,

n

2 , n ≤ f (a1, . . . , aj, n), si n > 1.

Algoritmos recursivos– p. 7

Por inducción

Hay que mostrar que T (k) ≤ f (a1, . . . , aj, k) para
1 ≤ k < n.
Cuando está establecido, resulta que

T (n) ≤ gT n

2 , n

≤ gfa1, . . . , aj, n
2 , n
≤ f (a1, . . . , aj, n), si n > 1.

Algoritmos recursivos– p. 8

Aplicación iterativa

Otra opcion es aplicar la ecuación recursiva de una
manera iterativa.
Por ejemplo, con la ecuación diferencial

obtenemos por aplicación repetida

T (1) = c1,
2 + c2n.
T (n) ≤ 2T n
2 + c2n ≤ 22T (n/4) + c2n

2 + c2n

T (n) ≤ 2T n

= 4T (n/4) + 2c2n ≤ 4 (2T (n/8) + c2n/4) + 2c2n
= 8T (n/8) + 3c2n.

Algoritmos recursivos– p. 9

La adivinanza

Observando la forma en que abre la ecuación, podemos
adivinar que por lo general aplica

T (n) ≤ 2iT n
En ese momento tenemos T n

2i + ic2n ∀i.
2k = T (1), o sea

Si asumimos que n = 2k, la recursión acaba cuando i = k.

T (n) ≤ 2kT (1) + kc2n.

Algoritmos recursivos– p. 10

De la condición 2k = n sabemos que

k = log n.

Entonces, con T (1) ≤ c1 obtenemos

o sea

T (n) ≤ c1n + c2n log n

T (n) ∈ O (n log n) .

El resultado

Algoritmos recursivos– p. 11

Solución general

En forma más general:

T (1) = 1

T (n) = a(n/b) + d(n),
donde a y b son constantes y d : Z+ → R+.
Para simplificar la situación, se supone que n = bk por
algún k ≥ 0 (o sea k = log b).

Algoritmos recursivos– p. 12

Representación

La solución necesariamente tiene la representación
siguiente:

T (n) =

+

parte homogénica

ak

|{z}

ajd(bk−j)

.

parte heterogénica

k−1

Xj=0
|

{z

}

En el caso que d(n) ≡ 0, no habrá parte heterogénica.

Algoritmos recursivos– p. 13

Demostración por descomposición

T (n) = aTn
= aaT n
= a2T n
...
= akT n

b + d(n)
b + d(n)
b2 + d n
b2 + ad n
b + d(n)
bk−1 + . . . + d(n)
bk + ak−1d n
Xj=0

ajd(bk−j)

k−1

= akT (1) +

= ak +

k−1

Xj=0

ajd(bk−j).

Algoritmos recursivos– p. 14

Parte homogénica

Para la parte homogénica ak aplica que
ak = alogb n = nlogb a.
En el análisis de ordenación por fusión tenemos a = b = 2,
en cual caso ak = n.

Algoritmos recursivos– p. 15

d multiplicativa

Si d es multiplicativa, o sea d(xy) = d(x)d(y), aplica que
d(bk−j) = (d(b))k−j que nos permite reformular la parte
heterogénica:

k−1

ajd(b)k−j = d(b)k

Xj=0
= d(b)k a
d(b)k
− 1
d(b) − 1

a

=

k−1

d(b)j
Xj=0 a
ak − d(b)k
d(b) − 1

.

a

Algoritmos recursivos– p. 16

Forma general

Entonces, cuando d es multiplicativo, tenemos

si
si
si

a > d(b)
a < d(b)
a = d(b).

Onlogb a ,
Onlogb d(b) ,
Onlogb d(b) logb n ,

T (n) =

En especial, si a < d(b) y d(n) = nα, tenemos
T (n) ∈ O (nα).
Si en vez a = d(b) y d(n) = nα, tenemos
T (n) ∈ O (nα logb n).

Algoritmos recursivos– p. 17

Demostración a > d(n)

Sea a > d(b). La parte heterogénica es entonces

a

ak − d(b)k
d(b) − 1 ∈ Oak ,

por lo cual T (n) ∈ Oak = Onlogb a, porque

ak = alogb n = nlogb a.
En este caso la parte homogénica y la parte heterogénica
son practicamente iguales.

Algoritmos recursivos– p. 18

Demostración a ≤ d(b)

En el caso que a < d(b), la parte heterogénica es Od(b)k
y T (n) ∈ Od(b)k = Onlogb d(b), porque

d(b)k = d(b)logb n = nlogb d(b).
Si a = d(b), tenemos para la parte heterogénica que

k−1

k−1

ajd(b)k−j = d(b)k

Xj=0 a
d(b)j

Xj=0
por lo cual T (n) ∈ Od(b)k k = Onlogb d(b) logb n.

k−1

Xj=0

= d(b)k

1j = d(b)kk,

Algoritmos recursivos– p. 19

Ejemplos

T (1) = 1, T (n) = 4T n
T (1) = 1, T (n) = 4T n
T (n) ∈ On2 log n
T (1) = 1, T (n) = 4T n
T (n) ∈ On3

2 + n =⇒ T (n) ∈ On2
2 + n2 =⇒
2 + n3 =⇒

En todos estos ejemplos a = 4 y b = 2, por lo cual la parte
homogénica es para todos alogb n = nlogb a = n2.

Algoritmos recursivos– p. 20

Estimación

Incluso se puede estimar la parte heterogénica en algunos
casos donde d no es multiplicativa.
Por ejemplo, en

T (1) = 1
T (n) = 3T n

2 + 2n1,5

d(n) = 2n1,5 no es multiplicativa, mientras n1,5 sóla lo es.

Algoritmos recursivos– p. 21

Ejemplo continua

Usamos la notación U (n) = T (n)
Entonces

2 para todo n.

U (1) = 1
2

U (n) = T (n)

2 =

22
3T n

+ n1,5 = 3Un

2 + n1,5.

Algoritmos recursivos– p. 22

Análisis del ejemplo

2 nlog 3.

2 tendríamos 1

Si tuvieramos que U (1) = 1, tendríamos una parte
homogénica 3log n = nlog 3.
En el caso U (1) = 1
En la parte heterogénica, el valor de U (1) no tiene ningún
efecto.
=⇒ a = 3 y b = 2
=⇒ d(b) = b1,5 ≈ 2, 82
=⇒ d(b) < a
=⇒ La parte heterogénica es Onlog 3.
=⇒ U (n) ∈ Onlog 3
Con T (n) = 2 U (n) =⇒ T (n) ∈ Onlog 3

Algoritmos recursivos– p. 23

Otro ejemplo

T (1) = 1
T (n) = 2T n

2 + n log n

donde la parte homogénica es ak = 2log n = nlog 2 = n.

Algoritmos recursivos– p. 24

Estimación directa

d(n) = n log n no es multiplicativa, por lo cual habrá que
estimar directamente la parte heterogénica:

ajd(bk−j) =

k−1

Xj=0

k−1

2j2k−j log 2k−j = 2k

Xi=0
= 2k (k + (k − 1) + (k − 2) + . . . + 1)
= 2k k(k+1)

2 = 2k−1k(k + 1).

k−1

Xj=0

k − j

Algoritmos recursivos– p. 25

Asignación k = log n

2k−1k(k + 1) = 2log n−1 log n(log n + 1)
2 )(log2 n + log n)

= 2log( n
= n

2 (log2 n + log n),

=⇒ La parte heterogénica es On log2 n.

Algoritmos recursivos– p. 26

Método de expansión

El método de expansión facilita la computación
involucrada en abrir una ecuación recursiva.
Ejemplo:

R(1) = 1
R(n) = 2 R(n − 1) + n, donde n ≥ 2.

Algoritmos recursivos– p. 27

Descomposición

R(n) = 2R(n − 1) + n

= 2(2R(n − 2) + n − 1) + n
= 4R(n − 2) + 3 n − 2
= 4(2R(n − 3) + n − 2) + 3 n − 2
= 8R(n − 3) + 7 n − 10
= . . .

Algoritmos recursivos– p. 28

La expansión

R(n)
R(n − 1)
R(n − 2)

R(n − i)

= 2R(n − 1) + n
= 2R(n − 2) + (n − 1)
= 2R(n − 3) + (n − 2)
...
= 2R(n − i − 1) + (n − i)
...

| × 1
| × 2
| × 4

| × 2i

R(n − (n − 2)) = 2R(1) + 2

| × 2n−2

Algoritmos recursivos– p. 29

Multiplicar y sumar

n−1

Multiplicamos por los coeficientes del lado izquiera y sumamos:
R(n) = 2n−1R(1) + n + 2(n − 1) + 4(n − 2) + . . . + 2n