07 Análisis de algoritmos recursivos - eafranco.com

Tema 06: Análisis de algoritmos recursivos

1

Análisis de algoritmos

M. en C. Edgardo Adrián Franco Martínez http://[email protected]@edfrancom edgardoadrianfrancom

http://www.eafranco.com/

mailto:[email protected]

• Recursividad• Ecuaciones en recurrencia• Ejemplo 01: Factorial recursivo• Ejemplo 02: Fibonacci recursivo• Ejemplo 03: Torres de Hanói recursivo• Ejemplo 04: Búsqueda binaria recursiva

• Recurrencias homogéneas• Ejemplo

• Recurrencias no homogéneas• Ejemplo

• Recurrencias no lineales• Teorema maestro

• Ejemplo 01• Ejemplo 02

Contenido

2

An

ális

is d

e al

gori

tmo

s0

6 A

nál

isis

de

algo

ritm

os

recu

rsiv

os

Pro

f. Ed

gard

o A

dri

án F

ran

co M

artí

nez

Recursividad• La recursividad es un

concepto fundamental enmatemáticas y encomputación. Es unaalternativa diferente paraimplementar estructuras derepetición (iteración).

• Se puede usar en todasituación en la cual lasolución pueda serexpresada como unasecuencia de movimientos,pasos o transformacionesgobernadas por un conjuntode reglas no ambiguas.

3

An

ális

is d

e al

gori

tmo

s0

6 A

nál

isis

de

algo

ritm

os

recu

rsiv

os

Pro

f. Ed

gard

o A

dri

án F

ran

co M

artí

nez

• La recursividad es un recurso muy poderoso quepermite expresar soluciones simples y naturales aciertos tipos de problemas. Es importanteconsiderar que no todos los problemas sonnaturalmente recursivos.

• Un objeto recursivo es aquel que aparece en ladefinición de si mismo, así como el que se llama así mismo.

4

An

ális

is d

e al

gori

tmo

s0

6 A

nál

isis

de

algo

ritm

os

recu

rsiv

os

Pro

f. Ed

gard

o A

dri

án F

ran

co M

artí

nez

• La recursividad es un fenómeno que se presenta enmuchos problemas de forma natural, delegando lasolución de un problema en la solución de otro máspequeño.

• El análisis temporal de un algoritmo recursivo vendráen función del tiempo requerido por la(s) llamada(s)recursiva(s) que aparezcan en él.

• El análisis temporal de un algoritmo iterativo essimple con base en la operación básica de este, paralos algoritmos recursivos nos vamos a encontrar conuna dificultad añadida, pues la función que establecesu tiempo de ejecución viene dada por una ecuaciónen recurrencia, es decir, 𝑻(𝒏) = 𝑬(𝒏), en donde enla expresión 𝐸 aparece la propia función 𝑻.

5

An

ális

is d

e al

gori

tmo

s0

6 A

nál

isis

de

algo

ritm

os

recu

rsiv

os

Pro

f. Ed

gard

o A

dri

án F

ran

co M

artí

nez

• Cuando se quiere calcular la demanda de recursosde un algoritmo definido recursivamente, la funcióncomplejidad que resulta no está definida sólo entérminos del tamaño del problema y algunasconstantes, sino en términos de la funcióncomplejidad misma.

• Además no es una sola ecuación, dado que existenotras (al menos una) que determinan la cantidad derecursos para los casos base de los algoritmosrecursivos. Dada esta situación, para poder obtenerel comportamiento del algoritmo, es necesarioresolver el sistema recurrente obtenido.

Ecuaciones en recurrencia

6

An

ális

is d

e al

gori

tmo

s0

6 A

nál

isis

de

algo

ritm

os

recu

rsiv

os

Pro

f. Ed

gard

o A

dri

án F

ran

co M

artí

nez

• Considerando el producto de num*Factorial(num-1)comooperación básica, y el costo del caso base como 1 (𝐓 𝟎 = 𝟏), podemosconstruir la ecuación recurrente para calcular la complejidad delalgoritmo como sigue:

𝑇 𝑛 = 1 + 𝑇(𝑛 − 1)𝑇 0 = 1

Ejemplo 01: Factorial recursivo

7

An

ális

is d

e al

gori

tmo

s0

6 A

nál

isis

de

algo

ritm

os

recu

rsiv

os

Pro

f. Ed

gard

o A

dri

án F

ran

co M

artí

nez

int Factorial( int num )

{

if ( num == 0 )

return 1;

else

return num * Factorial( num - 1 );

}

Costo de la multiplicación

Costo de la llamada a Factorial (n-1)

Costo del caso base

• Considerando la suma Fibonacci(num-1) + Fibonacci (num-2)

como operación básica, y el costo 1 de los 2 casos base podemosconstruir la ecuación recurrente para calcular la complejidad delalgoritmo.

𝑇 𝑛 = 𝑇 𝑛 − 1 + 1 + 𝑇 𝑛 − 2𝑇 0 = 1𝑇 1 = 1

Ejemplo 02: Fibonacci recursivo

8

An

ális

is d

e al

gori

tmo

s0

6 A

nál

isis

de

algo

ritm

os

recu

rsiv

os

Pro

f. Ed

gard

o A

dri

án F

ran

co M

artí

nez

int Fibonacci(int num)

{

if (num ==0)

return 0;

else if (num == 1)

return 1;

else

return Fibonacci(num-1) + Fibonacci (num-2);

}

Costo de la llamada a Fibonacci(n-1)

Costo de la llamada a Fibonacci(n-2)

Costo de la suma

Costo de n=0 y n=1

• Considerando la operación Mover_de(Src,Dst)como operación básica, ytomado un coste de 0 cuando N=0, podemos construir la ecuaciónrecurrente para calcular la complejidad del algoritmo.

𝑇 𝑛 = 𝑇 𝑛 − 1 + 1 + 𝑇 𝑛 − 1𝑇 0 = 0

Ejemplo 03: Torres de Hanói recursivo

9

An

ális

is d

e al

gori

tmo

s0

6 A

nál

isis

de

algo

ritm

os

recu

rsiv

os

Pro

f. Ed

gard

o A

dri

án F

ran

co M

artí

nez

Hanoi(N, Src, Aux, Dst)

{

if(n>0)

{

Hanoi(N - 1, Src, Dst, Aux);

Mover_de(Src,Dst);

Hanoi(N - 1, Aux, Src, Dst);

}

return;

}

• Considerando la operación como operación básica las comparaciones, ytomado un coste de 0 cuando Tam(numeros[])=0, podemos construir laecuación recurrente para calcular la complejidad del algoritmo.

𝑇 𝑛 = 3 + 𝑇 𝑛/2𝑇 0 = 0

Ejemplo 04: Búsqueda binaria recursiva

10

An

ális

is d

e al

gori

tmo

s0

6 A

nál

isis

de

algo

ritm

os

recu

rsiv

os

Pro

f. Ed

gard

o A

dri

án F

ran

co M

artí

nez

int BusquedaBinaria(int num_buscado, int numeros[], int inicio, int centro, int final)

{

if (inicio>final)

return -1;

else if (num_buscado == numeros[centro])

return centro;

else if (num_buscado < numeros[centro])

return BusquedaBinaria(num_buscado,numeros,inicio,(int)((inicio+centro-1)/2),centro-1);

else

return BusquedaBinaria(num_buscado,numeros,centro+1,(int)((final+centro+1)/2),final);

}

• Sea A un arreglo de n elementos y p, r índices del rango a ordenar.

𝑇 𝑛 = 2𝑇 𝑛/2 + 𝑛𝑇 1 = 1

Ejemplo 05: Merge-sort

11

An

ális

is d

e al

gori

tmo

s0

6 A

nál

isis

de

algo

ritm

os

recu

rsiv

os

Pro

f. Ed

gard

o A

dri

án F

ran

co M

artí

nez

Merge-Sort(a, p, r){

if ( p < r ){

q = parteEntera((p+r)/2);Merge-Sort(a, p, q);Merge-Sort(a, q+1,r);Merge(a, p, q, r);

}}

• Son de la forma:

𝑎0𝑇(𝑛) + 𝑎1𝑇(𝑛 − 1) + 𝑎2𝑇(𝑛 − 2) + … + 𝑎𝑘𝑇(𝑛 − 𝑘) = 0

• Donde los coeficientes 𝑎𝑖 son números reales, y 𝑘 es unnúmero natural entre 1 y 𝑛.

• Para eliminar la recurrencia se buscan términos que seancombinaciones de funciones exponenciales de la forma:

𝑇 𝑛 = 𝑐1𝑝1 𝑛 𝑟1𝑛 + 𝑐2𝑝2 𝑛 𝑟2

𝑛+…+𝑐𝑘𝑝𝑘 𝑛 𝑟𝑘𝑛 = σ𝑖=1

𝑘 𝑐𝑖𝑝𝑖1 𝑛 𝑟𝑖𝑛

• Donde los valores 𝑐1, 𝑐2, … , 𝑐𝑛 y 𝑟1, 𝑟2, … , 𝑟𝑛 son númerosreales, y 𝑝1(𝑛), … , 𝑝𝑘(𝑛) son polinomios en 𝑛 con coeficientesreales.

Recurrencias homogéneas

12

An

ális

is d

e al

gori

tmo

s0

6 A

nál

isis

de

algo

ritm

os

recu

rsiv

os

Pro

f. Ed

gard

o A

dri

án F

ran

co M

artí

nez

𝑎0𝑇(𝑛) + 𝑎1𝑇(𝑛 − 1) + 𝑎2𝑇(𝑛 − 2) + … + 𝑎𝑘𝑇(𝑛 − 𝑘) = 0

• Para resolverlas haremos el cambio 𝑥𝑘 = 𝑇(𝑛), conlo cual obtenemos la ecuación característicaasociada:

𝑎0𝑥𝑘 + 𝑎1𝑥

𝑘−1 + 𝑎2𝑥𝑘−2 + … + 𝑎𝑘 = 0

• Llamemos 𝑟1, 𝑟2, … , 𝑟𝑘 a sus raíces, ya sean reales ocomplejas. Dependiendo del orden de multiplicidadde tales raíces, pueden darse los siguientes casos:

• Caso 1: Raíces distintas

• Caso 2: Raíces con multiplicidad mayor que 1 13

An

ális

is d

e al

gori

tmo

s0

6 A

nál

isis

de

algo

ritm

os

recu

rsiv

os

Pro

f. Ed

gard

o A

dri

án F

ran

co M

artí

nez

Caso 1: Raíces distintas

• Si todas las raíces de la ecuación característica sondistintas, esto es, 𝑟𝑖 ≠ 𝑟𝑗 si 𝑖 ≠ 𝑗 , entonces la

solución de la ecuación en recurrencia viene dadapor la expresión:

𝑇 𝑛 = 𝑐1𝑟1𝑛 + 𝑐2𝑟2

𝑛+…+𝑐𝑘𝑟𝑘𝑛 = σ𝑖=1

𝑘 𝑐𝑖𝑟𝑖𝑛

• Donde los coeficientes 𝑐𝑖 se determinan a partirde las condiciones iniciales.

14

An

ális

is d

e al

gori

tmo

s0

6 A

nál

isis

de

algo

ritm

os

recu

rsiv

os

Pro

f. Ed

gard

o A

dri

án F

ran

co M

artí

nez

Caso 2: Raíces con multiplicidad mayor que1Supongamos que alguna de las raíces (p.e. 𝑟1) tienemultiplicidad 𝑚 > 1 . Entonces la ecuacióncaracterística puede ser escrita en la forma:

𝑥 − 𝑟1𝑚 𝑥 − 𝑟2 …(𝑥 − 𝑟𝑘−𝑚+1)

• En cuyo caso la solución de la ecuación enrecurrencia viene dada por la expresión:

𝑇 𝑛 =

𝑖=1

𝑚

𝑐𝑖𝑛𝑖−1𝑟𝑖

𝑛 +

𝑖=𝑚+1

𝑘

𝑐𝑖𝑟𝑖−𝑚+1𝑛

• Donde los coeficientes 𝑐𝑖 se determinan a partirde las condiciones iniciales.

15

An

ális

is d

e al

gori

tmo

s0

6 A

nál

isis

de

algo

ritm

os

recu

rsiv

os

Pro

f. Ed

gard

o A

dri

án F

ran

co M

artí

nez

• Este caso puede ser generalizado, si 𝑟1, 𝑟2, … , 𝑟𝑘son las raíces de la ecuación característica de unaecuación en recurrencia homogénea, cada unade multiplicidad 𝑚𝑖 , esto es, si la ecuacióncaracterística puede expresarse como:

(𝑥 − 𝑟1)𝑚1(𝑥 − 𝑟2)

𝑚2… 𝑥 − 𝑟𝑘𝑚𝑘 = 0

• Entonces la solución a la ecuación en recurrenciaviene dada por la expresión:

𝑇 𝑛 = σ𝑖=1𝑚1 𝑐1𝑖𝑛

𝑖−1𝑟1𝑛 +σ𝑖=1

𝑚1 𝑐2𝑖𝑛𝑖−1𝑟2

𝑛+…+σ𝑖=1𝑚k 𝑐k𝑖𝑛

𝑖−1𝑟k𝑛

• Donde los coeficientes 𝑐𝑖 se determinan a partir delas 𝑘 condiciones iniciales.

16

An

ális

is d

e al

gori

tmo

s0

6 A

nál

isis

de

algo

ritm

os

recu

rsiv

os

Pro

f. Ed

gard

o A

dri

án F

ran

co M

artí

nez

Recurrencias homogéneas (Ejemplo)

17

An

ális

is d

e al

gori

tmo

s0

6 A

nál

isis

de

algo

ritm

os

recu

rsiv

os

Pro

f. Ed

gard

o A

dri

án F

ran

co M

artí

nez• Se tiene la siguiente ecuación de recurrencia

𝑇 𝑛 = 5𝑇 𝑛– 1 – 8𝑇 𝑛– 2 + 4𝑇 𝑛– 3 , 𝑛 ≥ 2𝑇 𝑘 = 𝑘 para 𝑘 = 0, 1, 2

• Reordenando términos𝑇 𝑛 − 5𝑇 𝑛– 1 + 8𝑇 𝑛– 2 − 4𝑇 𝑛– 3 = 0

• Haciendo el cambio 𝑥3 = 𝑇(𝑛) obtenemos su ecuacióncaracterística 𝑥3 − 5𝑥2 + 8𝑥 − 4 = 0 , lo que es igual a(𝑥 − 2)2 𝑥 − 1 = 0, por lo tanto: 𝑟1=2, 𝑟2=2 y 𝑟3=1

𝑇 𝑛 = 𝑐12𝑛 + 𝑐2𝑛2

𝑛 + 𝑐31𝑛

• De las condiciones iniciales obtenemos:

𝑐1 = 2, 𝑐2 = –1

2𝑦 𝑐3 = –2

𝑻 𝒏 = 𝟐𝒏+𝟏 − 𝒏𝟐𝒏−𝟏 − 𝟐 ∈ 𝑶(𝒏𝟐𝒏)

• Son de la forma:

𝑎0𝑇(𝑛) + 𝑎1𝑇(𝑛 − 1) + 𝑎2𝑇(𝑛 − 2) + … + 𝑎𝑘𝑇(𝑛 − 𝑘) = 𝑏𝑛𝑝(𝑛)

• Donde los coeficientes 𝑎𝑖 y 𝑏 son números reales, y 𝑝(𝑛) es unpolinomio en 𝑛 de grado 𝑑.

• Para resolver este tipo de ecuaciones generalmente sedeben manipular para llegar a una ecuación homogénea.Una formula general para resolverla es mediante laecuación característica:

(𝑎0𝑥𝑘 + 𝑎1𝑥

𝑘−1 + 𝑎2𝑥𝑘−2 + … + 𝑎𝑘)(𝑥 − 𝑏)𝑑+1= 0

• Lo que nos lleva a aplicar el método para las recurrenciashomogéneas.

Recurrencias no homogéneas

18

An

ális

is d

e al

gori

tmo

s0

6 A

nál

isis

de

algo

ritm

os

recu

rsiv

os

Pro

f. Ed

gard

o A

dri

án F

ran

co M

artí

nez

• Generalizando este proceso, si tenemos una ecuaciónde la forma:

𝑎0𝑇 𝑛 + 𝑎1𝑇 𝑛 − 1 + 𝑎2𝑇 𝑛 − 2 + … + 𝑎0𝑇 𝑛 − 𝑘 = 𝑏1𝑛𝑝1 𝑛 + 𝑏2

𝑛𝑝2 𝑛 +⋯+ 𝑏𝑠𝑛𝑝𝑠 𝑛

• Donde los coeficientes 𝑎𝑖 y 𝑏𝑗son números reales, y 𝑝𝑗(𝑛)

son polinomios en 𝑛 de grado 𝑑𝑗

• La ecuación característica es:

(𝑎0𝑥𝑘 + 𝑥𝑘−1 + 𝑎2𝑥

𝑘−2 + … + 𝑎𝑘) 𝑥 − 𝑏1𝑑1+1 𝑥 − 𝑏2

𝑑2+1… 𝑥 − 𝑏𝑠𝑑𝑠+1 = 0

19

An

ális

is d

e al

gori

tmo

s0

6 A

nál

isis

de

algo

ritm

os

recu

rsiv

os

Pro

f. Ed

gard

o A

dri

án F

ran

co M

artí

nez

Recurrencias no homogéneas (Ejemplo)

20

An

ális

is d

e al

gori

tmo

s0

6 A

nál

isis

de

algo

ritm

os

recu

rsiv

os

Pro

f. Ed

gard

o A

dri

án F

ran

co M

artí

nez• Se tiene la siguiente ecuación de recurrencia

𝑇 𝑛 = 5𝑇 𝑛– 1 – 8𝑇 𝑛– 2 + 4𝑇 𝑛– 3 + 2𝑛3𝑛, 𝑛 ≥ 2𝑇 𝑘 = 𝑘 para 𝑘 = 0, 1, 2

• Reordenando términos𝑇 𝑛 − 5𝑇 𝑛– 1 + 8𝑇 𝑛– 2 − 4𝑇 𝑛– 3 = 2𝑛3𝑛

• Haciendo el cambio 𝑥3 = 𝑇 𝑛 , 𝑏 = 2 y 𝑑 = 1obtenemos su ecuación característica (𝑥3 − 5𝑥2+8𝑥 −4)(𝑥 − 2)2= 0 , lo que es igual a (𝑥 − 2)2()

𝑥 −1 (𝑥 − 2)2= 0, por lo tanto: 𝑟1=2, 𝑟2=2, 𝑟3=1, 𝑟4=2 y𝑟5=2

• Si 𝑐4 ≠ 0𝑇 𝑛 = 𝑐12

𝑛 + 𝑐2𝑛2𝑛 + 𝑐3𝑛

22𝑛 +𝑐4 𝑛32𝑛 + 𝑐51

𝑛 ∈ 𝑶(𝒏𝟑𝟐𝒏)

𝑇 𝑛 = 1 + 𝑇 𝑛 − 1 ; 𝑛 > 0𝑇 0 = 1

• Reordenando términos𝑇 𝑛 − 𝑇 𝑛– 1 = 1

• Haciendo el cambio 𝑥𝑘=1 = 𝑇 𝑛 , 𝑏 = 1 y 𝑑 = 0 obtenemos su ecuacióncaracterística (𝑥 − 1)(𝑥 − 1) = 0, lo que es igual a (𝑥 − 1)2 = 0, por lotanto: 𝑟1=1y 𝑟2=1.

𝑇 𝑛 = 𝑐1 + 𝑐2𝑛

• Si 𝑇 0 = 1 y 𝑇 1 = 2 𝑐1 = 1, 𝑐2 = 1

𝑻 𝒏 = 𝟏 + 𝒏 ∈ 𝑶(𝒏)

Ejemplo 01: Factorial recursivo

21

An

ális

is d

e al

gori

tmo

s0

6 A

nál

isis

de

algo

ritm

os

recu

rsiv

os

Pro

f. Ed

gard

o A

dri

án F

ran

co M

artí

nezint Factorial( int num )

{

if ( num == 0 )

return 1;

else

return num * Factorial( num - 1 );

}

Ejemplo 02: Fibonacci recursivo

22

An

ális

is d

e al

gori

tmo

s0

6 A

nál

isis

de

algo

ritm

os

recu

rsiv

os

Pro

f. Ed

gard

o A

dri

án F

ran

co M

artí

nez

¿Cuántas operaciones básicas se requieren para calcular:

f(4)?

f(3)?

f(2)?

f(1)?

f(0)?

--> 9

--> 5

--> 3

--> 1

--> 1

Relación:

El término T(n) requiere T(n-1)+1+T(n-2)

términos para calcularse.

T(0)=1

T(1)=1

Function fibonacci (n:int): int;

if (n=0) return 0;

else if (n=1) return 1;

else return fibonacci(n-1) + fibonacci(n-2);

f(4)

f(3)

f(2) f(1)

f(2)

f(1) f(0)

f(1) f(0)

23

An

ális

is d

e al

gori

tmo

s0

6 A

nál

isis

de

algo

ritm

os

recu

rsiv

os

Pro

f. Ed

gard

o A

dri

án F

ran

co M

artí

nez

• La ecuación en recurrencia definida para la sucesiónde Fibonacci con las condiciones iniciales:

𝑇 0 = 1 y 𝑇(1) = 1.

𝑇 𝑛 = 𝑇 𝑛– 1 + 𝑇 𝑛– 2 + 1, 𝑛 ≥ 2

• Reordenando términos𝑇 𝑛 − 𝑇 𝑛– 1 − 𝑇 𝑛– 2 = 1

• Haciendo el cambio 𝑥𝑘=1 = 𝑇 𝑛 , 𝑏 = 1 y 𝑑 = 0obtenemos su ecuación característica

• (𝑥2−𝑥 − 1)(𝑥 − 1) = 0, cuyas raíces son:

𝑟1 =1+ 5

2, 𝑟2 =

1− 5

2, 𝑟3 = 1

• Y por lo tanto 𝑇 𝑛 = 𝑐11+ 5

2

𝑛

+ 𝑐21− 5

2

𝑛

+ 𝑐3

24

An

ális

is d

e al

gori

tmo

s0

6 A

nál

isis

de

algo

ritm

os

recu

rsiv

os

Pro

f. Ed

gard

o A

dri

án F

ran

co M

artí

nez

• Para calcular las constantes 𝑐1, 𝑐2 y 𝑐3 necesitamos utilizar lascondiciones iniciales de la ecuación original, obteniendo:

𝑇 0 = 𝑐11+ 5

2

0

+ 𝑐21− 5

2

0

+ 𝑐3 = 𝑐1 + 𝑐2 + 𝑐3 = 1

𝑇 1 = 𝑐11 + 5

2

1

+ 𝑐21 − 5

2

1

+ 𝑐3 = 1

𝑇 2 = 𝑐11 + 5

2

2

+ 𝑐21 − 5

2

2

+ 𝑐3 = 3

𝑇 𝑛 = 𝑐11 + 5

2

𝑛

+ 𝑐21 − 5

2

𝑛

+ 𝑐3

• Si 𝑐1 o 𝑐2 no valen 0 se tendrá ∈ Ο(𝑐𝑛)

25

An

ális

is d

e al

gori

tmo

s0

6 A

nál

isis

de

algo

ritm

os

recu

rsiv

os

Pro

f. Ed

gard

o A

dri

án F

ran

co M

artí

nez

𝜑 =1+ 5

2≈1.6180339887498948482045868343656… (número áureo)

El número áureo surge de la división en dos de un segmento guardando las siguientes proporciones: La longitud total a+b es al segmento más largo a, como a es al segmento más corto b.

Ejemplo 03: Torres de Hanói

26

An

ális

is d

e al

gori

tmo

sC

lase

s 1

2 y

13

: A

nál

isis

de

algo

ritm

os

recu

rsiv

os

Pro

f. Ed

gard

o A

dri

án F

ran

co M

artí

nez

Operación básica movimiento de cero o un disco

𝑇(0) = 0𝑇(1) = 1

Solve(N, Src, Aux, Dst)

if N is 0

exit

else

Solve(N - 1, Src, Dst, Aux)

Move from Src to Dst

Solve(N - 1, Aux, Src, Dst)

T(n-1)

T(n-1)

1

• 𝑻 𝒏 = 𝟐𝑻 𝒏–𝟏 + 𝟏 𝐬𝐢 𝐧 > 𝟎

• Acomodando los términos se tiene:𝑇 𝑛 − 2𝑇 𝑛– 1 = 1

(𝑎0𝑥𝑘 + 𝑥𝑘−1 + 𝑎2𝑥

𝑘−2 + … + 𝑎𝑘)(𝑥 − 𝑏)𝑑+1= 0

• No homogénea con 𝑏 = 1, 𝑝(𝑛) = 0 𝑦 𝑑 = 0;

27

An

ális

is d

e al

gori

tmo

sC

lase

s 1

2 y

13

: A

nál

isis

de

algo

ritm

os

recu

rsiv

os

Pro

f. Ed

gard

o A

dri

án F

ran

co M

artí

nez

• (𝑎0𝑥𝑘 + 𝑥𝑘−1 + 𝑎2𝑥

𝑘−2 + … + 𝑎𝑘)(𝑥 − 𝑏)𝑑+1= 0

• 𝑇 𝑛 − 2𝑇 𝑛– 1 = 1; 𝑏 = 1, 𝑝(𝑛) = 0 𝑦 𝑑 = 0

• Su Ecuación característica es:𝑥 − 2 (𝑥 − 1) = 0

• Por lo tanto

𝑇 𝑛 = 𝑐12𝑛+𝑐21

𝑛 ∈ Θ(2𝑛)

𝐶𝑜𝑛 𝑙𝑜𝑠 𝑐𝑎𝑠𝑜𝑠 𝑖𝑛𝑖𝑐𝑖𝑎𝑙𝑒𝑠𝑇(0) = 0𝑇(1) = 1

𝐸𝑛𝑐𝑜𝑛𝑡𝑟𝑎𝑚𝑜𝑠𝑐1=1𝑐2=-1

𝑇 𝑛 = 2𝑛 − 1 ∈ Θ(2𝑛)

𝑥1 = 2𝑥2 = 1

Sustituir como raíces distintas

• El teorema maestro es un método matemático que se usa pararesolver ciertos casos particulares de ecuaciones de recurrenciacomo la siguiente:

𝑇 𝑛 = 𝑎𝑇𝑛

𝑏+ 𝑓(𝑛)

• Donde el coeficientes 𝑎 ≥ 1 y 𝑏 >1 y𝑛

𝑏puede ser tomada como

𝑛

𝑏o

𝑛

𝑏entonces 𝑇 𝑛 tiene los siguientes limites asintóticos :

1. Si 𝑓 𝑛 = 𝑂(𝑛log𝑏 𝑎−𝜀) para alguna 𝜀 > 0, entonces

• 𝑻 𝒏 = 𝜣 𝒏𝐥𝐨𝐠𝒃 𝒂

2. Si 𝑓 𝑛 = Θ 𝑛log𝑏 𝑎 , entonces

• 𝑻 𝒏 = 𝜣 𝒏𝐥𝐨𝐠𝒃 𝒂𝐥𝐠(𝒏)

3. Si 𝑓 𝑛 = Ω 𝑛log𝑏 𝑎+𝜀 para alguna 𝜀 > 0 y si 𝑎𝑓 𝑛/𝑏 ≤ 𝑐𝑓(𝑛),para alguna constante 𝑐 < 1 y suficientemente grandes 𝑛 entonces

• 𝑻 𝒏 = 𝜣(𝒇(𝒏))

Recurrencias no lineales

28

An

ális

is d

e al

gori

tmo

s0

6 A

nál

isis

de

algo

ritm

os

recu

rsiv

os

Pro

f. Ed

gard

o A

dri

án F

ran

co M

artí

nez

Logaritmos

• Un logaritmo es un exponente o potencia, ala que un número fijo (llamado base), se hade elevar para dar un cierto número.

• Entonces, el logaritmo es la función inversade la función exponente.

loga c = b

ab = c 29

An

ális

is d

e al

gori

tmo

s0

6 A

nál

isis

de

algo

ritm

os

recu

rsiv

os

Pro

f. Ed

gard

o A

dri

án F

ran

co M

artí

nez

• log2(n) = el exponente a la que 2 se ha de elevar para obtener n.• P.g: log2(8) = 3 (porque 23 = 8)

• P.g: log2(1024) = 10 (porque 210 = 1024)

30

An

ális

is d

e al

gori

tmo

s0

6 A

nál

isis

de

algo

ritm

os

recu

rsiv

os

Pro

f. Ed

gard

o A

dri

án F

ran

co M

artí

nez

Propiedades de los logaritmos

31

1. El logaritmo de la base siempre es igual auno, es decir:

2. El logaritmo de 1 en cualquier base essiempre igual a cero:

3. El logaritmo de un producto es igual a lasuma de los logaritmos de sus factores:

loga a = 1

loga 1 = 0

loga (b·c) = loga b + loga c

An

ális

is d

e al

gori

tmo

s0

6 A

nál

isis

de

algo

ritm

os

recu

rsiv

os

Pro

f. Ed

gard

o A

dri

án F

ran

co M

artí

nez

32

4. El logaritmo de una fracción es igual a laresta del logaritmo del numerador menos ellogaritmo del denominador.

5. El logaritmo de una potencia es igual a lapotencia multiplicando al logaritmo de labase de la potencia:

6. El logaritmo de la base elevado a unapotencia es igual a la potencia.

loga (b/c) = loga b – loga c

loga bc = c loga b

loga ab = b

An

ális

is d

e al

gori

tmo

s0

6 A

nál

isis

de

algo

ritm

os

recu

rsiv

os

Pro

f. Ed

gard

o A

dri

án F

ran

co M

artí

nez

33

7. Cambio de base de logaritmo: El logaritmoen base a un número es igual a la fracciónentre el logaritmo del primer número conbase en un tercer número y el logaritmo delsegundo número con base en un tercernúmero.

8. Un número elevado al logaritmo con baseen el mismo número, es igual al número dellogaritmo.

loga b = logc b / logc a

a loga

b = b

An

ális

is d

e al

gori

tmo

s0

6 A

nál

isis

de

algo

ritm

os

recu

rsiv

os

Pro

f. Ed

gard

o A

dri

án F

ran

co M

artí

nez

34

𝑇(𝑛) = 9𝑇(𝑛/3) + 𝑛

𝑎 = 9, 𝑏 = 3, 𝑓(𝑛) = 𝑛 ⇒ 𝑛log𝑏 𝑎 = 𝑛log3 9 = Θ(𝑛2)∴ 𝑓(𝑛) = Ο(𝑛log3 9−𝜀), 𝜀 = 6

1. Si f(n) = Ω(nlogba+ε) para algún 𝜀 > 0, ysi 𝑎 𝑓(𝑛/𝑏) ≤ 𝑐 𝑓(𝑛) paraalguna constante c < 1y suficientemente grandes n,⇒ T(n) = Θ(f(n)).

)()( 2nnT =

Ejemplo 01 Uso del teorema maestro

An

ális

is d

e al

gori

tmo

s0

6 A

nál

isis

de

algo

ritm

os

recu

rsiv

os

Pro

f. Ed

gard

o A

dri

án F

ran

co M

artí

nez

𝑇(𝑛) = 9𝑇(𝑛/3) + 𝑛

35

𝑇(𝑛) = 𝑇(2𝑛/3) + 1 ⇒ 𝐶𝑎𝑠𝑜2

𝑎 = 1, 𝑏 = 3/2, 𝑓(𝑛) = 1 ⇒ 𝑛log𝑏 𝑎 = 𝑛log3/2 1 = 𝑛𝑜 = 1

1. Si f(n) = Ο(nlogba−ε) para algún 𝜀 > 0 ⇒ T(n) = Θ(nlogb𝑎)

2. Si f(n) = Θ(nlogb𝑎) ⇒ T(n) = Θ(nlogb𝑎 lg 𝑛)


)(lg)( nnT =


An

ális

is d

e al

gori

tmo

s0

6 A

nál

isis

de

algo

ritm

os

recu

rsiv

os

Pro

f. Ed

gard

o A

dri

án F

ran

co M

artí

nez

𝑇(𝑛) = 𝑇(2𝑛/3) + 1

36

𝑇(𝑛) = 2𝑇(𝑛/2) + 𝑛

𝑎 = 2, 𝑏 = 2, 𝑓(𝑛) = 𝑛 ⇒ 𝑛log𝑏 𝑎 = 𝑛log2 2 = 𝑛1 = n

f(n) = Θ(nlogb𝑎) ⇒ 𝐶𝑎𝑠𝑜2




(nlg(n)) T(n) =


An

ális

is d

e al

gori

tmo

s0

6 A

nál

isis

de

algo

ritm

os

recu

rsiv

os

Pro

f. Ed

gard

o A

dri

án F

ran

co M

artí

nez

𝑇(𝑛) = 2𝑇(𝑛/2) + 𝑛

37

𝑇 𝑛 = 2𝑇𝑛

2+ 𝑛2

𝑎 = 2, 𝑏 = 2, 𝑓 𝑛 = 𝑛2 = Θ 𝑛2 . ⇒ f n = Ω nlogba+ε

𝑛log𝑏 𝑎+2 = 𝑛log2 4 = 𝑛2

⇒ 𝐶𝑎𝑠𝑜3 ⇒ 𝑠𝑖 𝑓(𝑛/𝑏) ≤ 𝑐 𝑓(𝑛) ⇒ 𝑛/2 2 ≤ 𝑐 𝑛2 𝑝𝑎𝑟𝑎 𝑎𝑙𝑔𝑢𝑛𝑎 𝑐 < 1 ⇒ c=1/2T(n) = Θ(f(n)).




T(n) = Θ(𝑛2)


An

ális

is d

e al

gori

tmo

s0

6 A

nál

isis

de

algo

ritm

os

recu

rsiv

os

Pro

f. Ed

gard

o A

dri

án F

ran

co M

artí

nez

𝑇(𝑛) = 2𝑇(𝑛/2) + 𝑛2

Otra forma de ver el teorema maestro

38

An

ális

is d

e al

gori

tmo

s0

6 A

nál

isis

de

algo

ritm

os

recu

rsiv

os

Pro

f. Ed

gard

o A

dri

án F

ran

co M

artí

nez

07 Análisis de algoritmos recursivos - eafranco.com

Documents

Transcript of 07 Análisis de algoritmos recursivos - eafranco.com