PDF de programación - Análisis de Programas Recursivos

Arturo Díaz Pérez

Análisis y Diseño de Algoritmos

Análisis de Programas Recursivos

Arturo Díaz Pérez

‹ Introducción
› Programas Recursivos
fi Análisis de Funciones Recursivas
fl Relaciones de recurrencia para evaluar programas recursivos

Análisis y Diseño de Algoritmos

Análisis-1

Introducción

F Las reglas generales de análisis nos permiten analizar

programas y algoritmos con estructuras de control
convencionales

void Burbuja( int A[], int n)
{

i, j, temp;

int
for( i = 0; i < n-1; i++ )

}

}

for( j = n-1; j >= i+1; j-- )

if( A[j-1] > A[j] ) {

temp = A[j-1];
A[j-1] = A[j];
A[j] = temp;

O(1)

O(n)

O(n)

Análisis y Diseño de Algoritmos

Análisis-2

Análisis y Complejidad de Algoritmos

1

Arturo Díaz Pérez

Programas Recursivos

F En muchas ocasiones es “mejor” escribir algoritmos

(programas) recursivos
Claridad
Espacio
Elegancia

F Durante la década de los 70’s existían cursos sobre

programación recursiva

F La programación recursiva se utiliza ampliamente en los

lenguajes funcionales y programación lógica
LISP
Prolog
Mathematica
Maple

Análisis y Diseño de Algoritmos

Análisis-3

Ejemplo: Factorial de n

n! = n (n-1)!,
n! = 1

Si n > 0
Si n = 0

long factorial( long n )
{

if( n <= 0 )
return 1;

else

return n*factorial(n-1);

}

Análisis y Diseño de Algoritmos

Análisis-4

Análisis y Complejidad de Algoritmos

2

Arturo Díaz Pérez

MergeSort

n

n/2

n/2

Ordena

Ordena

Mezla

Análisis y Diseño de Algoritmos

Análisis-5

MergeSort

n

n/2

n/2

void Sort( int A, int n )
{

int A1[], A2[];

/* Divide a A en dos mitades, A1 y A2,

cada una de longitud n/2 */

if( n > 1 ) {

Sort( A1, n/2 );
Sort( A2, n/2 );
Mezcla( A1, A2, A);

Análisis y Diseño de Algoritmos

}

}

Análisis-6

Análisis y Complejidad de Algoritmos

3

Arturo Díaz Pérez

Las Torres de Hanoi

F Las torres de Hanoi

Se tienen 3 postes, A, B, y C. Inicialmente el poste A tiene
apilados un número de discos, iniciado con el diámetro más
grande en el fondo hasta el más pequeño en el tope.

El problema es mover los discos de un poste a otro, uno a la
vez, sin colocar nunca un disco de diámetro mayor sobre uno de
diámetro menor.

A

B

C

Análisis y Diseño de Algoritmos

Análisis-7

Las Torres de Hanoi

A

B

C

struct Poste P[3];

void Hanoi( int n, int A, int B, int C )
{

if(n > 1){

Hanoi(n-1, A, C, B);
MueveDisco(A, B);
Hanoi(n-1, C, B, A);

} else

}

MueveDisco(A,B);

Análisis y Diseño de Algoritmos

Análisis-8

Análisis y Complejidad de Algoritmos

4

Arturo Díaz Pérez

¿Cómo analizar algoritmos o programas recursivos?

Análisis y Diseño de Algoritmos

Análisis-9

Análisis de Funciones Recursivas

F Análisis

Con cada procedimiento recursivo se asocia una función de tiempo

desconocido T(n), donde n mide el tamaño de los argumentos al
procedimiento

Se puede obtener una recurrencia para T(n), esto es una ecuación para

T(n) en términos de T(k) para varios valores de k

/T(n) = ...T(k)...

Análisis y Diseño de Algoritmos

Análisis-10

Análisis y Complejidad de Algoritmos

5

Arturo Díaz Pérez

Análisis de Funciones Recursivas

long factorial( long n )
{

if( n <= 0 )
return 1;

else

return n*factorial(n-1);

}

)(
nT

=

+
nTc
(
d

)1

si
si

>

n
n

0
0

F Si n >2, se tiene que

T(n) = c + T(n-1) = c +c +T(n-2) = 2c +T(n-2)

F Si n >3

T(n) = 2c + T(n-2) = 2c + c + T(n-3) = 3c + T(n-3)

F En general, si n >i

T(n) = ic + T(n-i)

F Finalmente, si i = n-1

T(n) = (n-1)c + T(1) = (n-1)c + d

F de aquí se concluye que T(n) es un O(n)

Análisis y Diseño de Algoritmos

Análisis-11

MergeSort

void Sort( int A, int n )
{

int A1[], A2[];

if( n > 1 ) {

/* Divide a A en dos mitades, A1 y A2,

cada una de longitud n/2 */

Sort( A1, n/2 );
Sort( A2, n/2 );
Mezcla( A1, A2, A);

}

}

)(
nT

=

c
1
)(2
T
n
2

+

nc
2

si
si

n
n

1
1

>

Análisis y Diseño de Algoritmos

Análisis-12

Análisis y Complejidad de Algoritmos

6



£
-



£
Arturo Díaz Pérez

Resolución de Recurrencias

F Estrategias para resolver una recurrencia

Adivinar una solución

Transformar a alguna expresión con solución conocida

Calcular la fórmula cerrada
/Expandiendo la recurrencia

Análisis y Diseño de Algoritmos

Análisis-13

Adivinando una Solución

)(
nT

=

c
1
)(2
T
n
2

+

nc
2

si
si

n
n

1
1

>

F Supongamos que T(n) £ a n logn + b para algunas constantes a y b

F Probemos por inducción, que T(n) £ an log n + b (*)

a) Para n = 1, c1

£ alog1 + b

£ b

c1

Análisis y Diseño de Algoritmos

Análisis-14

Análisis y Complejidad de Algoritmos

7



£
Arturo Díaz Pérez

Adivinando una Solución
b) Supongamos que T(n) £ an log n + b (*) es válida para todo k <n.
Demostremos que se cumple también para n

/Se tiene que T(n) £ 2 T(n/2) + c2n
/Entonces

3 T(n) £ 2[a(n/2)log(n/2) +b] + c2n
3 T(n) £ an logn – an log2 + 2b + c2n
3 T(n) £ an logn - an + c2n +2b

/Por un lado,

3 Si a ‡ c2 + b
3 Si n ‡ 1

-an £
-bn £

-c2n – bn, y
-b

-c2n - bn £

-c2n - b

/Entonces, si a ‡ c2 +b y n ‡ 1, se tiene que -an +c2n +b £ 0
/Por lo tanto, T(n) £ an logn + b

Luego entonces, si b ‡ c1 y a ‡ c2 +b se tiene que T(n) £ an logn +b

F De aquí, T(n) es un O(nlog n)

Análisis y Diseño de Algoritmos

Observaciones

" n ‡ 1

Análisis-15

Si se supone que T(n) es un O(f(n)) y al intentar probar por inducción
que T(n) £ cf(n) no se tiene éxito, no se sigue de esto que T(n) no es un
O(f(n).

/En algunos casos una prueba por inducción de la forma

3 T(n) £ cf(n) - 1
puede tener éxito.

Análisis y Diseño de Algoritmos

Análisis-16

Análisis y Complejidad de Algoritmos

8



Arturo Díaz Pérez

Ejemplo

F Considere la recurrencia
T(n) = T(º n/2ß ) + T(Ø n/2ø ) + 1
Adivinamos que la solución es O(n).
Tratamos de mostrar que T(n) £ cn, para una constante c

apropiada.

= cn + 1.

T(n) £ c º n/2ß + Ø n/2ø ) + 1

Lo cual no implica que T(n) £ cn.
Tratemos ahora con T(n) £ cn - b, para constantes c y b ‡ 0.
(c º n/2ß -b) +(cØ n/2ø -b) + 1
T(n) £
= cn - 2b + 1.

£ cn - b, siempre que b ‡ 1.

Lo cual no implica que T(n) £ cn

Análisis y Diseño de Algoritmos

Análisis-17

Cambio de Variables

F Considere ahora la recurrencia

T(n) = 2T(Ø n ø ) + log2 n

Hagamos m = log2n, entonces, n = 2m y

/T(2m) = 2T(Ø 2m/2 ø ) + m

Esto es, S(m) = 2S(Ø m/2ø ) + m

Por lo tanto, S(m) = O(mlogm).

De aquí, T(n) = O(logn loglog n).

Análisis y Diseño de Algoritmos

Análisis-18

Análisis y Complejidad de Algoritmos

9

Arturo Díaz Pérez

Observaciones

Si se supone que T(n) es un O(f(n)) y al intentar probar por inducción
que T(n) £ cf(n) no se tiene éxito, no se sigue de esto que T(n) no es un
O(f(n).

/En algunos casos una prueba por inducción de la forma

3 T(n) £ cf(n) - 1
puede tener éxito.

Al adivinar que T(n) es un O(f(n)) no se garantiza que f(n) es la menor
cota superior al rango de crecimiento de T(n). Puede existir alguna otra
solución con un índice de crecimiento menor.

Análisis y Diseño de Algoritmos

Análisis-19

Técnica General

F Supongamos que se parte de la ecuación de recurrencia siguiente:

=

)1(
T
nT
)(

c
Tg
(

(

n
2

),

n

,)

>

1

n

F Supongamos además que se adivina la solución representada por la función:

( 1
af

,...,

),
na
l

la cual depende de los parámetros a1,a2, ..., al y de n.

F Entonces, se tendría que probar que

)(
nT

(
af
1

,...,

),
na
l

para todo n>n0 y para algunos valores de a1,a2, ..., al.

Análisis y Diseño de Algoritmos

Análisis-20

Análisis y Complejidad de Algoritmos

10

£
£
Arturo Díaz Pérez

Técnica General

F Así, se debe satisfacer que

(
af
1
(
af
1

,...,
,...,

)1,
a
l
),
na
l

c
(
(
afg
1

,...,

a
l

,

n
2

),

n

)

)(
i
)(
ii

F Así se obtendría que

y de aquí que

nT
)(

(
(
afg
1

,...
a

l

,

n
2

),

n

)

nT
)(

(
af
1

,...,

),
na
l

Análisis y Diseño de Algoritmos

Análisis-21

Expandiendo Recurrencias

F Si no se puede adivinar una solución o no se está seguro de que se ha encontrado la
mejor cota superior para T(n), se puede tratar de expandir la ecuación de recurrencia.

F Para el ejemplo, si n ‡ 2,

F Si n ‡ 4,

F Entonces

F Similarmente, si n ‡ 8,

£)(
nT
( )

T

n
2

£)(
nT

£)(
nT

£)(
nT

nc
2

c
n
22

n
2

( )
+
( )

n
4

+

T
2

2
T
[
T
22

( )

n
4

+

c
n
22

]

+

nc
2

=

T
4

( )

n
4

+

2

nc
2

( )

n
8

]

+

+

c
n
42

2

nc
2

[
T
24
( )

T
8

n
8

+

nc
3
2

Análisis y Diseño de Algoritmos

Análisis-22

Análisis y Complejidad de Algoritmos

11

£
‡
‡
£
£
Arturo Díaz Pérez

Expandiendo Recurrencias

F Se puede ver que si n ‡ 2i, se tiene que
i
2

£)(
nT

T

)

+

(

n
i
2

nic
2

F Suponiendo que n = 2k, este proceso termina tan pronto como se obtiene T(1) en la

parte derecha. Así

nT
)(

Tk

2

1
)(

+

nkc
2

F Ya que 2k = n

log2n = k. Como T(1) £ c1, entonces se cumple que

£)(
nT

+

ncnc
1
2

log

n

F De aquí que T(n) es un O(n logn)

Análisis y Diseño de Algoritmos

Análisis-23

Solución General

F Suponga que un problema de tamaño n se divide en a

subproblemas de tamaño n/b
se asume que un problema de tamaño 1 toma una unidad de tiempo
el tiempo para juntar las soluciones de los subproblemas para resolver

el problema de tamaño n toma un tiempo d(n)

Ecuación de recurrencia
1)1( =
T
=
nT
)(

aT

( )
n +
b

)(
nd

• esta ecuación sólo se aplica a n's que son potencias enteras de b.

• Si T(n) es suave, se obtiene una cota superior en T(n) para aquellos

valores de n (potencias enteras de b),

• Dice como crece T(n) en general

• d(n) es arbitra