Upload
others
View
11
Download
0
Embed Size (px)
Citation preview
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
• 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 𝑛)
3. Si f(n) = Ω(nlogba+ε) para algún 𝜀 > 0, ysi 𝑎 𝑓(𝑛/𝑏) ≤ 𝑐 𝑓(𝑛) paraalguna constante c < 1y suficientemente grandes n,⇒ T(n) = Θ(f(n)).
)(lg)( nnT =
Ejemplo 02 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
𝑇(𝑛) = 𝑇(2𝑛/3) + 1
36
𝑇(𝑛) = 2𝑇(𝑛/2) + 𝑛
𝑎 = 2, 𝑏 = 2, 𝑓(𝑛) = 𝑛 ⇒ 𝑛log𝑏 𝑎 = 𝑛log2 2 = 𝑛1 = n
f(n) = Θ(nlogb𝑎) ⇒ 𝐶𝑎𝑠𝑜2
1. Si f(n) = Ο(nlogba−ε) para algún 𝜀 > 0 ⇒ T(n) = Θ(nlogb𝑎)
2. Si f(n) = Θ(nlogb𝑎) ⇒ T(n) = Θ(nlogb𝑎 lg 𝑛)
3. Si f(n) = Ω(nlogba+ε) para algún 𝜀 > 0, ysi 𝑎 𝑓(𝑛/𝑏) ≤ 𝑐 𝑓(𝑛) paraalguna constante c < 1y suficientemente grandes n,⇒ T(n) = Θ(f(n)).
(nlg(n)) T(n) =
Ejemplo 03 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
𝑇(𝑛) = 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)).
1. Si f(n) = Ο(nlogba−ε) para algún 𝜀 > 0 ⇒ T(n) = Θ(nlogb𝑎)
2. Si f(n) = Θ(nlogb𝑎) ⇒ T(n) = Θ(nlogb𝑎 lg 𝑛)
3. Si f(n) = Ω(nlogba+ε) para algún 𝜀 > 0, ysi 𝑎 𝑓(𝑛/𝑏) ≤ 𝑐 𝑓(𝑛) paraalguna constante c < 1y suficientemente grandes n,⇒ T(n) = Θ(f(n)).
T(n) = Θ(𝑛2)
Ejemplo 04 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
𝑇(𝑛) = 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