03_Analise de algoritmos recursivos

Prévia do material em texto

1
Estrutura de Dados e 
Algoritmos
1
Análise de Algoritmos Recursivos
Prof. Cláudio Campelo, PhD
Departamento de Sistemas & Computação / UFCG
Perguntas pertinentes
2
� Quais são as características de um algoritmo
recursivo?
� Como encontrar o número de chamadas
recursivas?
� Como saber o tamanho da entrada de cada
chamada?
� Como analisar um algoritmo recursivo?
2
Background Matemático
3
� Somatórios
� Linearidade
∑
=
+++=
n
k
kk aaaa
1
21 ...
∑ ∑
∞
= =
∞→
=
1 1
lim
k
n
k
k
n
k aa
Background Matemático
4
� Progressão aritmética
� Progressão geométrica
),...,,,( 321 naaaa
rnaan ).1(1 −+=
,...)16,13,10,7,4,1(:Ex
2
)( 1 n
n
aanS +=
),...,,,( 321 naaaa ,...)64,32,16,8,4,2(:Ex
1
1.
−
=
n
n qaa
1
)1(1
−
−
=
q
qaS
n
n
Soma dos termos de uma PG finita crescente
1||,
1
1 <
−
=
∞
q
q
aS Soma dos termos de uma PG infinita decrescente
3
Background Matemático
5
� Logarítmos
baab ccc loglog)(log +=
abba log=
ana b
n
b log.log =
1log =aa
nnn 2loglglog ==
an bb na
loglog
=
a
bb
c
c
a log
loglog =
Relações de recorrência
6
� Equações ou inequações que descrevem uma função
em termos de seus valores (recursão) considerando
entradas menores (mais simples).
� Exemplo:
� Métodos de resolução a serem vistos: 
� Iterativo
� Mestre
� TODO algoritmo recursivo tem uma relação de 
recorrência associada!
4
Visão Geral: Análise de 
Algoritmos Recursivos
7
int XYZ(int n, …) { 
…
XYZ(…)
}
T(n)=T(n-..)...
Algoritmo Recursivo
Relação de 
Recorrência
Método Mestre
T = Θ(...)
n2
…
Θ(1)
n2
n2/2
…
n2/4 n2/4
n2/16 n2/4
n2/2
Método Iterativo
T(n) = aT(n/b) + f(n)
Se Caso 1
Se Caso 2
Se Caso 3
T = Θ(...)
T = Θ(...)
T = Θ(...)
Método Iterativo
8
� Intuição
MERGE-SORT(A)
if n = 1 done.
MERGE-SORT(A[1.. �n/2�]) 
MERGE-SORT(A[�n/2�+1..n])
“Merge” the 2 sorted lists
merge: O(n)
merge-sort(n/2)
merge-sort(n/2)
5
Método Iterativo
9
� Intuição
merge: O(n)
merge-sort(n/4)
merge: O(n/2)
merge-sort(n/4)
merge-sort(n/4)
merge: O(n/2)
merge-sort(n/4)
MERGE-SORT(A)
if n = 1 done.
MERGE-SORT(A[1.. �n/2�]) 
MERGE-SORT(A[�n/2�+1..n])
“Merge” the 2 sorted lists
Método Iterativo
10
� Árvore de recorrência
� Visualização conveniente da expansão de uma relação
de recorrência
processamento recursivo
das partes menores
combinar as respostas 
do processamento recursivo
6
Método Iterativo
11
� Árvore de recorrência
Série geométrica decrescente
)(
2
)2/1/(
)2/11/(
)1/(1
2
2
2
2
n
n
n
n
qaSn
Θ=
=
=
−=
−=
)2/1...4/12/11(2 hn nS ++++=
n grande � PG infinita
Número de chamadas
recursivas
Tamanho
da entrada
Encontrando Relação
12
MERGE-SORT(A)
if n = 1 done.
MERGE-SORT(A[ 1.. n/2 ]) 
MERGE-SORT(A[ n/2 +1..n ])
“Merge” the 2 sorted lists
Θ(1)
n é o tamanho de A
T(⌊n/2⌋)
T(�n/2�)
Θ(n)
T(n) = T(⌊n/2⌋) + T(�n/2�) + Θ(n)
T(n) = 2T(n/2) + Θ(n)
Abuso, mas não muda o 
resultado
7
Exercício 1
13
� Encontre a relação de recorrência do algoritmo a 
seguir.
int fatorial (int n) {
if (n == 0)
return 1;
else
return n * fatorial(n-1);
}
Exercício 1
14
� Encontre a relação de recorrência do algoritmo a 
seguir.
int fatorial (int n) {
if (n == 0)
return 1;
else
return n * fatorial(n-1);
}
8
Exercício 1
15
� Encontre a relação de recorrência do algoritmo a 
seguir.
T (n) {
if (n == 0)
return 1;
else
return n * T(n-1);
}
Exercício 1
16
� Encontre a relação de recorrência do algoritmo a 
seguir.
T (n) {
if (n == 0) T(1) = 1 
return 1; 
else
return n * T(n-1);
}
9
Exercício 1
17
� Encontre a relação de recorrência do algoritmo a 
seguir.
T (n) {
if (n == 0) Θ(1) 
return 1; 
else
return n * T(n-1);
}
Exercício 1
18
� Encontre a relação de recorrência do algoritmo a 
seguir.
T (n) {
Θ(1) 
T(n-1);
}
10
Exercício 1
19
� Encontre a relação de recorrência do algoritmo a 
seguir.
T (n) =
Θ(1) 
T(n-1);
Exercício 1
20
� Encontre a relação de recorrência do algoritmo a 
seguir.
T (n) = T(n-1) + Θ(1)
T (n) =
Θ(1) 
T(n-1);
11
Método Iterativo
21
� Como resolver a recorrência do merge sort?
T(n) =
Θ(1), se n=1
2T(n/2) + Θ(n), se n>1
Procedimento: Método Iterativo
22
1. Desenhe a árvore de recursão com base na
relação de recorrência (T) (EXPANSÃO)
2. Encontre a maior altura (h) até o caso base
3. Some os custos de cada nível
4. Analise o relacionamento entre os custos de cada 
nível (RESOLUÇÃO DE TERMOS)
5. Some o custo de todos os níveis com base na 
relação encontrada em 4. 
PA, PG (q>1), PG (q<1)?
12
Método Iterativo
23
� Como resolver a recorrência do merge sort?
� Que tal subtituir Θ(n) por cn ?
T(n) = 2T(n/2) + cn
T(n) =
Θ(1), se n=1
2T(n/2) + Θ(n), se n>1
Método Iterativo (Resolvendo os termos)
24
T(n)T(n) = 2T(n/2) + cn
13
Método Iterativo (Resolvendo os termos)
25
T(n) = 2T(n/2) + cn
T(n/2) T(n/2)
cn
Método Iterativo (Resolvendo os termos)
26
T(n/2) T(n/2)
cn
T(n) = 2T(n/2) + cn
T(n/2) = 2T(n/4) + cn/2
14
Método Iterativo (Resolvendo os termos)
T(n/4) T(n/4) T(n/4) T(n/4)
cn/2 cn/2
cn
T(n) = 2T(n/2) + cn
T(n/2) = 2T(n/4) + cn/2
Método Iterativo (Resolvendo os termos)
28
cn/4
cn/2 cn/2
cn
T(n/8) T(n/8) ...
T(n) = 2T(n/2) + cn
T(n/2) = 2T(n/4) + cn/2
T(n/4) = 2T(n/8) + cn/4
cn/4 cn/4 cn/4
... ...
15
Método Iterativo (Resolvendo os termos)
29
cn/4
cn/2 cn/2
cn
cn/8 cn/8 ...
T(n) = 2T(n/2) + cn
T(n/2) = 2T(n/4) + cn/2
T(n/4) = 2T(n/8) + cn/4
cn/4 cn/4 cn/4
... ...
...
cn/???
... ... ... ... ... ...
...
Método Iterativo (Resolvendo os termos)
30
cn/4
cn/2 cn/2
cn
cn/8 cn/8 ...
cn/4 cn/4 cn/4
... ...
...
cn/???
... ... ... ... ... ...
h=0
h=1
h=2
h=3
16
Método Iterativo (Resolvendo os termos)
31
cn/4
cn/2 cn/2
cn
cn/8 cn/8 ...
cn/4 cn/4 cn/4
... ...
...
cn/2h
... ... ... ... ... ...
h=0
h=1
h=2
h=3
Método Iterativo (Resolvendo os termos)
32
cn/4
cn/2 cn/2
cn
cn/8 cn/8 ...
cn/4 cn/4 cn/4
... ...
... ... ... ... ... ... ...
h=0
h=1
h=2
h=3
cn/2h = k )/log(/22 kcnhkcnk
cn h
h =⇒=⇒=⇒
17
Método Iterativo (Resolvendo os termos)
33
cn/4
cn/2 cn/2
cn
cn/8 cn/8 ...
cn/4 cn/4 cn/4
... ...
... ... ... ... ... ... ...
h=0
h=1
h=2
h=3
cn/2h = k )/log(/22 kcnhkcnk
cn h
h =⇒=⇒=⇒ h = log n
Método Iterativo (Resolvendo os termos)
34
cn/4
cn/2 cn/2
cn
cn/8 cn/8 ...
cn/4 cn/4 cn/4
...
... ... ... ... ... ...
h=0
h=1
h=2
h=3
cn/2h cnh.
cn
cn
cn
cn
cn
18
Método Iterativo (Resolvendo os termos)
35
cn/4
cn/2 cn/2
cn
cn/8 cn/8 ...
cn/4 cn/4 cn/4
...
... ... ... ... ... ...
h=0
h=1
h=2
h=3
cn/2h )log()(log. nncnncnh Θ⇒⇒
cn
cn
cn
cn
cn
Exercício 2
36
� Utilize o método iterativo (utilizando a árvore de 
recursão para visualização) para resolver a 
recorrência a seguir:
T(n) = 3T(n/2) + n2
T = O(n2)
19
Exercício 3
37
� Faça um algoritmo recursivo que realize uma busca 
sequencial em um elemento de um vetor. Qual a 
relação de recorrência? 
� Utilize o método iterativo (árvore de recursão) para 
resolver a recorrência.
T(n) = T(n-1) + Θ(1)
T = O(n)
Método Mestre
38
� Provê um livro de receitas paraum bom número
de recorrências da forma:
� Onde a≥1 e b>1 são constantes e f(n) é uma 
função assintoticamente positiva. 
� Os a problemas são resolvidos recursivamente 
em T(n/b) e o tempo de dividir e combinar os 
resultados dos subproblemas é dado por f(n).
T(n) = aT(n/b) + f(n)
a=Número de 
subproblemas
b=Tamanho do 
subproblema
20
Comparação Básica do Método
39
f(n) <
f(n) =
f(n) >
Caso 1
Caso 2
Caso 3
T(n) = aT(n/b) + f(n)
)()( log abnnT Θ=
))(()( nfnT Θ=
)log).((
)log()( log
nnf
nnnT
b
b
ab
Θ=
Θ=
Teorema Mestre (Caso 1)
40
T(n) = aT(n/b) + f(n)
Exemplo:
8log2n
8log2 21000 nn <
21
Procedimento: Método Mestre
41
1. Identifique a, b, f(n), log a
2. Verifique as condições sobre a≥1 e b>1 e f(n)
3. Compare f(n) com para identificar o caso
4. Confirme a condição do caso 
5. Encontre o Θ
b
Teorema Mestre (Caso 2)
42
T(n) = aT(n/b) + f(n)
Exemplo:
2log2n
2log210 nn =
22
Teorema Mestre (Caso 3)
43
T(n) = aT(n/b) + f(n)
Exemplo:
2log2n
2log2 2nn >
Exercício 4
44
� O método mestre pode ser aplicado nas seguintes 
recorrências? Justifique. 
23
Exercício 4
45
� O método mestre pode ser aplicado nas seguintes 
recorrências? Justifique. 
a=2n não é constante
a=0.5<1
f(n) não é não-negativa
X
X
X
Exercício 5
46
� Indique o limite assintoticamente restrito da 
recorrência T(n) = 2T(n/2) + n utilizando o método 
mestre
24
Exercício 6
47
� Uma busca binária acontece em arrays ordenados. 
� Se o elemento a ser buscado é o do meio do array
então a busca termina. Senão
� Se o elemento buscado é menor do que o elemento do 
meio então a busca se dá na primeira metade. Senão a 
busca se dá na segunda metade. 
boolean search(int x, int v[], int l, int r) { 
int m = (l + r) / 2; 
if (l > r) return false; 
if (x == v[m]) return m; 
if (x < v[m]) return search(x, v, l, m-1); 
else return search(x, v, m+1, r); 
} 
T(n) = T(n/2)+c
Θ(log n)
Exercício 7
48
� Considerando uma entrada ordenada. Qual dos 
algoritmos você escolheria para uma busca: 
seqüencial ou binária? Considere os algoritmos 
implementados anteriormente.
25
Referências
49
� Capítulos 1-4
� 1a edição
� 2a edição