03 Analise de algoritmos recursivos

Prévia do material em texto

ESTRUTURAS DE DADOS E ALGORITMOS
ANÁLISE DE ALGORITMOS RECURSIVOS
Adalberto Cajueiro
Departamento de Sistemas e Computação
Universidade Federal de Campina Grande
1
PERGUNTAS PERTINENTES
 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
 Somatórios
 Propriedades úteis



n
k
kk aaaa
1
21 ...
 

 


1 1
lim
k
n
k
k
n
k aa
3
BACKGROUND MATEMÁTICO
 Progressão aritmética
 Progressão geométrica
),...,,,( 321 naaaa
rnaan ).1(1 
,...)16,13,10,7,4,1(:Ex
2
)( 1 n
n
aan
S


),...,,,( 321 naaaa
,...)64,32,16,8,4,2(:Ex
1
1.
 nn qaa
1
)1(1



q
qa
S
n
n
Soma dos termos de uma PG finita crescente
1||,
1
1 

 q
q
a
S
Soma dos termos de uma PG infinita decrescente
4
BACKGROUND MATEMÁTICO
 Logarítmos
baab ccc loglog)(log 
abba
log
ana b
n
b log.log 
1log aa
nnn 2loglglog 
an bb na
loglog 
a
b
b
c
c
a
log
log
log 
5
(mudança de base)
acka kc log
(definição)
Usando a definição, 
mudança de base e 
propriedades da exponenciação,
tente mostrar essas propriedades
RELAÇÕES DE RECORRÊNCIA
 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! 6
VISÃO GERAL: ANÁLISE DE ALGORITMOS
RECURSIVOS
7
int XYZ(int n, …) { 
…
XYZ(n’,…)
}
T(n)=T(f(n)..)...
Algoritmo Recursivo
Relação de 
Recorrência
Método Mestre
T(n) = aT(n/b) + f(n)
, onde ε>0
c<1
, onde ε>0
, então
T = Θ(n2)
n2
…
Θ(1)
n2
n2/2
…
n2/4 n2/4
n2/16 n
2/4
n2/2...
altura=log2(n)
Método Iterativo
ENCONTRAR RELAÇÃO DE RECORRÊNCIA
 Apenas algoritmos recursivos possuem uma relação de 
recorrência associada.
8
int fatorial (int n) {
if (n == 0)
return 1;
else
return n * fatorial(n-1);
}
ENCONTRAR RELAÇÃO DE RECORRÊNCIA
9
int fatorial (int n) {
if (n == 0)
return 1;
else
return n * fatorial(n-1);
}
ENCONTRAR RELAÇÃO DE RECORRÊNCIA
10
T (n) {
if (n == 0)
return 1;
else
return n * T(n-1);
}
ENCONTRAR RELAÇÃO DE RECORRÊNCIA
11
T (n) {
if (n == 0)
return 1; T(1) = 1
else
return n * T(n-1);
}
ENCONTRAR RELAÇÃO DE RECORRÊNCIA
12
T (n) {
if (n == 0)
return 1; (1)
else
return n * T(n-1);
}
ENCONTRAR RELAÇÃO DE RECORRÊNCIA
13
T (n) =
(1) +
T(n-1)
ENCONTRAR RELAÇÃO DE RECORRÊNCIA
14
T (n) =
(1) +
T(n-1)
T (n) = T(n-1) + (1)
E agora? Como resolver a relação acima?
PROCEDIMENTO: MÉTODO ITERATIVO
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. Resolva os termos da árvore descobrindo os 
custos de combinar as respostas em cada nó 
(RESOLUÇÃO DE TERMOS)
4. Some os custos de cada nível
5. Some o custo de todos os níveis e use algum 
artifício matemático se necessário: PA, PG 
(q>1), PG (q<1)?
15
MÉTODO ITERATIVO (EXPANDINDO A ÁRVORE)
16
T(n) = 2T(n/2) + cn
T(n/2) T(n/2)
Visualização:
Árvore de Recursão
T(n)
17
T(n/2) T(n/2)
T(n) = 2T(n/2) + cn
MÉTODO ITERATIVO (EXPANDINDO A ÁRVORE)
T(n)
MÉTODO ITERATIVO (EXPANDINDO A ÁRVORE)
18
T(n/2) T(n/2)
T(n/2) = 2T(n/4) + cn/2 T(n/2) = 2T(n/4) + cn/2
T(n)
T(n) = 2T(n/2) + cn
MÉTODO ITERATIVO (EXPANDINDO A ÁRVORE)
19
T(n/4) T(n/4) T(n/4) T(n/4)
T(n/2) = 2T(n/4) + cn/2 T(n/2) = 2T(n/4) + cn/2
T(n/2) T(n/2)
T(n)
T(n) = 2T(n/2) + cn
MÉTODO ITERATIVO (EXPANDINDO A ÁRVORE)
20
T(n/4) T(n/4) T(n/4) T(n/4)
T(n/2) = 2T(n/4) + cn/2 T(n/2) = 2T(n/4) + cn/2
T(n/2) T(n/2)
T(n)
T(n) = 2T(n/2) + cn
T(n/4) = 2T(n/8) + cn/4
MÉTODO ITERATIVO (EXPANDINDO A ÁRVORE)
21
T(n/4) T(n/4) T(n/4) T(n/4)
T(n/2) = 2T(n/4) + cn/2 T(n/2) = 2T(n/4) + cn/2
T(n/2) T(n/2)
T(n)
T(n) = 2T(n/2) + cn
T(n/4) = 2T(n/8) + cn/4
T(n/8) T(n/8) ...
...
MÉTODO ITERATIVO (EXPANDINDO A ÁRVORE)
22
T(n/4) T(n/4) T(n/4) T(n/4)
T(n/2) T(n/2)
T(n)
T(n/8) T(n/8) ...
h=0
h=1
h=2
h=3
h=...
...
T(n/2h)
MÉTODO ITERATIVO (EXPANDINDO A ÁRVORE)
23
T(n/4) T(n/4) T(n/4) T(n/4)
T(n/2) T(n/2)
T(n)
T(n/8) T(n/8) ...
h=0
h=1
h=2
h=3
h=...
...
T(n/2h)
T(n) =
(1), se n=1
2T(n/2) + (n), se n>1
MÉTODO ITERATIVO (EXPANDINDO A ÁRVORE)
24
T(n/4) T(n/4) T(n/4) T(n/4)
T(n/2) T(n/2)
T(n)
T(n/8) T(n/8) ...
h=0
h=1
h=2
h=3
h=...
...
T(n/2h) = c
cnhcnhcnc
n h
h
 log)/log(/2
2
MÉTODO ITERATIVO (EXPANDINDO A ÁRVORE)
25
T(n/4) T(n/4) T(n/4) T(n/4)
T(n/2) T(n/2)
T(n)
T(n/8) T(n/8) ...
h=0
h=1
h=2
h=3
h=...
...
T(n/2h) = 1
nhn
n h
h
log21
2

MÉTODO ITERATIVO (RESOLVENDO OS
TERMOS)
26
T(n/4) T(n/4) T(n/4) T(n/4)
T(n/2) T(n/2)
T(n)
T(n/8) T(n/8) ...
...
T(n/2h)
T(n) = 2T(n/2) + cn
MÉTODO ITERATIVO (RESOLVENDO OS
TERMOS)
27
T(n/4) T(n/4) T(n/4) T(n/4)
T(n/2) T(n/2)
cn
T(n/8) T(n/8) ...
...
T(n/2h)
T(n) = 2T(n/2) + cn
MÉTODO ITERATIVO (RESOLVENDO OS
TERMOS)
28
T(n/4) T(n/4) T(n/4) T(n/4)
T(n/2) T(n/2)
cn
T(n/8) T(n/8) ...
...
T(n/2h)
T(n) = 2T(n/2) + cn
T(n/2) = 2T(n/4) + cn/2
MÉTODO ITERATIVO (RESOLVENDO OS
TERMOS)
29
T(n/4) T(n/4) T(n/4) T(n/4)
cn/2 cn/2
cn
T(n/8) T(n/8) ...
...
T(n/2h)
T(n) = 2T(n/2) + cn
T(n/2) = 2T(n/4) + cn/2
MÉTODO ITERATIVO (RESOLVENDO OS
TERMOS)
30
T(n/4)
cn/2 cn/2
cn
T(n/8) T(n/8) ...
...
T(n/2h)
T(n) = 2T(n/2) + cn
T(n/2) = 2T(n/4) + cn/2
T(n/4) = 2T(n/8) + cn/4
T(n/4) T(n/4) T(n/4)
MÉTODO ITERATIVO (RESOLVENDO OS
TERMOS)
31
cn/4
cn/2 cn/2
cn
T(n/8) T(n/8) ...
...
T(n/2h)
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
MÉTODO ITERATIVO (RESOLVENDO OS
TERMOS)
32
cn/4
cn/2 cn/2
cn
...
...
cn/???
cn/4 cn/4 cn/4
cn/8 cn/8
h=0
h=1
h=2
h=3
h=log n
MÉTODO ITERATIVO (RESOLVENDO OS
TERMOS)
33
cn/21
cn
...
...
h=0
h=1
h=2
h=3
h=log n
cn/21
cn/22 cn/22 cn/22 cn/22
cn/23
cn/2h
MÉTODO ITERATIVO (SOMANDO OS CUSTOS
POR ALTURA)
34
cn/21
cn
...
...
h=0
h=1
h=2
h=3
h=log n
cn/21
cn/22 cn/22 cn/22 cn/22
cn/23
cn/2h
cn
cn
cn
…
cn
+
+ + +
+
MÉTODO ITERATIVO (SOMANDO OS CUSTOS
POR ALTURA)
35
cn/21
cn
...
...
h=0
h=1
h=2
h=3
h=log n
cn/21
cn/22 cn/22 cn/22 cn/22
cn/23
cn/2h
cn
cn
cn
…
cn )log()(log. nncnncnh 
+
+ + +
+
ALGORITMO MERGESORT
 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)
36
ALGORITMO MERGESORT
 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/4)
merge: O(n/2)
merge-sort(n/4)
merge-sort(n/4)
merge: O(n/2)
merge-sort(n/4)
37Número de chamadas
recursivas
Tamanho
da entrada
ALGORITMO MERGESORT
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
38
Θ(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
ALGORITMO MERGESORT
 Como resolver a recorrência do merge sort?
 Que tal usar no lugar de 
2T(n/2) + (n)?
39
T(n) = 2T(n/2) + cn
T(n) =
(1), se n=1
2T(n/2) + (n), se n>1
EXERCÍCIO 1
 Utilize o método iterativo (utilizando a árvore de 
recursão para visualização) para resolver a 
recorrência a seguir:
40
T(n) = 2T(n/2) + n2
T = O(n2)
EXERCÍCIO 2
 Utilize o método iterativo (utilizando a árvore de 
recursão para visualização) para resolver a 
recorrência a seguir:
41
T(n) = 3T(n/2) + n2
T = O(n2)
EXERCÍCIO 3
 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.
42
T(n) = T(n-1) + Θ(1)
T = O(n)
MÉTODO MESTRE
 Provê um livro de receitas para um 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 sao resolvidos recursivamente 
em T(n/b) e o tempo de dividir e combinar os 
resultados dos subproblemas é dado por f(n).
43
T(n) = aT(n/b) + f(n)
a=Número de 
subproblemas
b=Tamanho do 
subproblema
COMPARAÇÃO BÁSICA DO MÉTODO
44
f(n) <
f(n) =
f(n) >
Caso 1
Caso 2
Caso 3
Só a parte 
polinomial
T(n) = aT(n/b) + f(n)
)()(
log abnnT 
))(()( nfnT 
)log).((
)log()(
log
nnf
nnnT
b
b
ab


TEOREMA MESTRE (CASO 1)
45
T(n) = aT(n/b) + f(n)
Exemplo:
8log2n
8log2 21000 nn 
PROCEDIMENTO: MÉTODO MESTRE
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 Θ
46
b
TEOREMA MESTRE (CASO 2)
47
T(n) = aT(n/b) + f(n)
Exemplo:
2log2n
2log210 nn 
TEOREMA MESTRE (CASO 3)
48
T(n) = aT(n/b) + f(n)
Exemplo:
2log2n
2log2 2nn 
EXERCÍCIO 1
 O método mestre pode ser aplicado nas seguintes 
recorrências? Justifique. 
49
EXERCÍCIO 1
 O método mestre pode ser aplicado nas seguintes 
recorrências? Justifique. 
50
a=2n não é constante
a=0.5<1
f(n) não é não-negativa
EXERCÍCIO 2
 Indique o limite assintoticamente restrito da recorrência 
T(n) = 2T(n/2) + n utilizando o método mestre
51
EXERCÍCIO 3
 Uma busca binaria acontece em arrays ordenados. 
 Se o elemento a ser buscado é o do meio do array entao 
a busca termina. Senao
 Se o elemento buscado é menor do que o elemento do meio 
entao a busca se dá na primeira metade. Senao a busca se 
dá na segunda metade. 
52
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 4
 Considerando uma entrada ordenada. Qual dos 
algoritmos você escolheria para uma busca: 
seqüencial ou binária? Considere os algoritmos 
implementados anteriormente.
53
REFERÊNCIAS
 Capítulos 1-4
 1a edição
 2a edição
54