Buscar

AEDSII_aula_009_analise_algoritmos_recursivos

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 31 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 31 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 31 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

Algoritmos e Estrutura de Dados II 
Análise de Algoritmos Recursivos 
n  Para cada procedimento recursivo é 
associada uma função de complexidade f(n) 
desconhecida, onde n mede o tamanho dos 
argumentos para o procedimento. 
n  Por se tratar de um algoritmo recursivo, f(n) 
vai ser obtida através de uma equação de 
recorrência. 
n  Equação de recorrência: maneira de definir 
uma função por uma expressão envolvendo 
a mesma função. 
Algoritmos e Estrutura de Dados II 
Análise de Algoritmos Recursivos 
n  Tempo de execução de um algoritmo 
recursivo: tamanho, número de 
subproblemas e o tempo para 
decomposição. 
n  Capturado pela equação de recorrência. 
⎩
⎨
⎧
≤=
>+=
 cnknT
 cn nfbnaTnT
 para ,)(
 para ),()/()(
Algoritmos e Estrutura de Dados II 
Equação de Recorrência 
Fat (int n) { 
 if (n <= 0) 
 return 1; 
 else 
 return n * Fat(n-1); 
} 
Algoritmos e Estrutura de Dados II 
Fat (int n) { 
 if (n <= 0) 
 return 1; 
 else 
 return n * Fat(n-1); 
} 
n  Equação de recorrência para o Fatorial 
T(n) = c + T(n-1), para n > 0 
T(n) = d. para n ≤ 0 
Equação de Recorrência 
Algoritmos e Estrutura de Dados II 
Equação de Recorrência 
void max(int *v, int e, int d){ 
int u, v; 
int m = (e+d)/2; 
 
 if (e == d) return v[e]; 
 u = max(v, e, m); 
 v = max(v, m+1, d); 
 if (u > v) return u; 
 else return v; 
} 
Algoritmos e Estrutura de Dados II 
Equação de Recorrência 
void max(int *v, int e, int d){ 
int u, v; 
int m = (e+d)/2; 
 
 if (e == d) return v[e]; 
 u = max(v, e, m); 
 v = max(v, m+1, d); 
 if (u > v) return u; 
 else return v; 
} 
T(n) = 2T(n/2) + 1, para n > 1 
T(n) = 0. para n ≤ 1 
Algoritmos e Estrutura de Dados II 
Exercício 1 
n  Determine a equação de recorrência para a 
função abaixo (operação relevante: atribuição 
para vetor X). 
void ex(vetor X, int n){ 
 int i; 
 
 if (n > 0) { 
 for(i=0; i<n-1; i++) 
 X[i] = 0; 
 X[n] = n; 
 ex(X,n-1); 
 } 
} 
Algoritmos e Estrutura de Dados II 
Exercício 1 
n  Determine a equação de recorrência para a 
função abaixo (operação relevante: atribuição 
para vetor X). 
void ex(vetor X, int n){ 
 int i; 
 
 if (n > 0) { 
 for(i=0; i<n-1; i++) 
 X[i] = 0; 
 X[n] = n; 
 ex(X,n-1); 
 } 
} ⎩
⎨
⎧
≤=
>−+=
0 para ,0)(
0 para ),1()(
nnT
 n nTnnT
Algoritmos e Estrutura de Dados II 
Outro Exemplo 
n  Considere a seguinte função: 
Pesquisa(n) 
{ 
(1) if (n <= 1) 
(2) ‘ inspecione elemento ’ e termine; 
 else 
 { 
(3) para cada um dos n elementos ‘ inspecione 
elemento’; 
(4) Pesquisa(n/3) ; 
 } 
} 
Algoritmos e Estrutura de Dados II 
Outro Exemplo 
n  Considere a seguinte função: 
Pesquisa(n) 
{ 
(1) if (n <= 1) 
(2) ‘ inspecione elemento ’ e termine; 
 else 
 { 
(3) para cada um dos n elementos ‘ inspecione elemento’; 
(4) Pesquisa(n/3) ; 
 } 
} 
⎩
⎨
⎧
≤=
>+=
1 para ,1)(
1 para ),3/()(
nnT
 n nTnnT
Algoritmos e Estrutura de Dados II 
Análise de Algoritmos Recursivos 
n  Abordagem para solução da recorrência: 
q  Expande a árvore de recursão 
q  Calcula o custo em cada nível da árvore 
q  Soma os custos de todos os níveis 
q  Calcula a fórmula fechada do somatório 
Algoritmos e Estrutura de Dados II 
Fat (int n) { 
 if (n <= 0) 
 return 1; 
 else 
 return n * Fat(n-1); 
} 
n  Equação de recorrência para o Fatorial 
T(n) = c + T(n-1), para n > 0 
T(n) = d. para n ≤ 0 
Equação de Recorrência 
Algoritmos e Estrutura de Dados II 
Equação de Recorrência 
Fat (int n) { 
 if (n <= 0) 
 return 1; 
 else 
 return n * Fat(n-1); 
} 
n  Se n <= 0 faz uma operação de custo 
constante 
n  Se n > 0 faz uma operação de custo 
constante e chama recursivamente a função 
Algoritmos e Estrutura de Dados II 
Equação de Recorrência 
Fat (int n) { 
 if (n <= 0) 
 return 1; 
 else 
 return n * Fat(n-1); 
} 
n  Equação de recorrência para o Fatorial 
T(n) = c + T(n-1), para n > 0 
T(n) = d. para n ≤ 0 
Algoritmos e Estrutura de Dados II 
Resolvendo a Equação de Recorrência 
n  Existem várias formas de se resolver uma equação 
de recorrência 
n  A mais simples é expandir a equação e depois fazer 
uma substituição dos termos 
n  Ex. Fatorial: 
T(n) = c + T(n-1) 
T(n-1) = c + T(n-2) 
T(n-2) = c + T(n-3) 
... 
T(1) = c + T(0) 
T(0) = d 
T(n) = c + c + c + ... + c + d 
n vezes 
T(n) = n.c + d à O(n) 
Algoritmos e Estrutura de Dados II 
Equação de Recorrência 
void max(int *v, int e, int d){ 
int u, v; 
int m = (e+d)/2; 
 
 if (e == d) return v[e]; 
 u = max(v, e, m); 
 v = max(v, m+1, d); 
 if (u > v) return u; 
 else return v; 
} 
T(n) = 2T(n/2) + 1, para n > 1 
T(n) = 0. para n ≤ 1 
Algoritmos e Estrutura de Dados II 
Exercício 1 
n  Determine a equação de recorrência para a 
função abaixo (operação relevante: atribuição 
para vetor X). Qual a sua complexidade? 
void ex(vetor X, int n){ 
 int i; 
 
 if (n > 0) { 
 for(i=0; i<n-1; i++) 
 X[i] = 0; 
 X[n] = n; 
 ex(X,n-1); 
 } 
} ⎩
⎨
⎧
≤=
>−+=
0 para ,0)(
0 para ),1()(
nnT
 n nTnnT
Algoritmos e Estrutura de Dados II 
Outro Exemplo 
n  Equação : 
n  Essa equação lembra que tipo de problema? 
n  Como resolver essa equação? 
T(n) = 2T(n/2) + n; 
T(1) = 1; 
T(n) = 2T(n/2) + n; 
T(1) = 1; 
Algoritmos e Estrutura de Dados II 
Resolvendo a Equação 
)log.(log.).(log1.2.)2(2)(
:Logo
log12
)1()2(
:Parada de Condição acolocar Para
.)2(2)(
: termosos doSubstituin
)2(2)2(2
)8(8)4(4
)4(4)2(2
)2(2)(
:equação a Expandindo
1)1(
)2(2)(
222
log
2
11
2 nnOnnnnnninTnT
nin
TnT
ninTnT
nnTnT
nnTnT
nnTnT
nnTnT
T
nnTnT
nii
i
i
ii
iiii
=+=+=+=
=→=
→
+=
+=
+=
+=
+=
=
+=
−−

Algoritmos e Estrutura de Dados II 
Exercício 
n  Considere a seguinte função: 
Pesquisa(n) 
{ 
(1) if (n <= 1) 
(2) ‘ inspecione elemento ’ e termine; 
 else 
 { 
(3) para cada um dos n elementos ‘ inspecione 
elemento’; 
(4) Pesquisa(n/3) ; 
 } 
} 
Algoritmos e Estrutura de Dados II 
Análise da Função Recursiva 
n  Equação de recorrência 
 
 
 
n  Resolva a equação de recorrência 
q  Dicas: 
q  Pode fazer a simplificação de n será sempre 
divisível por 3 
q  Somatório de uma PG finita: 
 
 
∑
=
+
−
−
=
n
i
n
i
r
rr
0
1
1
1
⎩
⎨
⎧
≤=
>+=
1 para ,1)(
1 para ),3/()(
nnT
 n nTnnT
Algoritmos e Estrutura de Dados II 
Resolvendo a equação 
n  Substitui-se os termos T(k), k < n, até que todos os termos 
T(k), k > 1, tenham sido substituídos por fórmulas contendo 
apenas T(1). 
1 → n/3K = 1 → n = 3K 1 
Algoritmos e Estrutura de Dados II 
Resolvendo a equação 
 Considerando que T(n/3K) = T(1) temos: 
 
 
 
 Aplicando a fórmula do somatório de uma PG 
finita temos: 
 
 
O(n) 
∑
=
+
−
−
=
n
i
n
i
r
rr
0
1
1
1
1
3
1)1(
3
)(
1
0
1
0
+=+= ∑∑
−
=
−
=
k
i
i
k
i
i nT
nnT
2123
)3/2()1(1
)3/2())/1(1(1
)3/11())3/1(1(1
−
−+
−+
−−+
n
n
nn
n k
Algoritmos e Estrutura de Dados II 
Teorema Mestre 
n  Método “receita de bolo” para resolver 
recorrências do tipo 
n  Este tipo de recorrência é típico de 
algoritmos“dividir para conquistar” 
q  Dividem um problema em a subproblemas 
q  Cada subproblema tem tamanho n/b 
q  Custo para dividir e combinar os resultados é f(n) 
positiva  )(  e  ,  onde
)()/()(
nfba
nfbnaTnT
11 >≥
+=
Algoritmos e Estrutura de Dados II 
Teorema Mestre 
n  Seja 
 
)()/()( nfbnaTnT +=
)).((Θ)(  temos                        
,  para  )()/(  se  e    para  )(Ω)(  Se
).log(Θ)(  temos                        
,)(Θ)(  Se
).(Θ)(  temos                        
,  com  ,)()(  Se
log
log
log
log
log
nfnT
cncfbnafnnf
nnnT
nnf
nnT
nOnf
a
a
a
a
a
b
b
b
b
b
=
<≤>=
=
=
=
>=
+
−
10
0
�
�
�
�
Algoritmos e Estrutura de Dados II 
Teorema Mestre 
n  O resultado da recorrência depende da 
comparação entre 
n  Note que a diferença entre 
tem que ser polinomial, isto é, tem que ser 
pelo menos 
abnnf log  e  )(
abnnf log  e  )(
�n
Teorema Mestre (1) 
n  Resolva a recorrência 
usando o teorema mestre 
n  Caso 1 se aplica, temos 
nnTnT += )/()( 39
)(Θ)( 2nnT =
)).(()( temos 
,1 para )()/( se e 0 para )()( Se 3.
).log()( temos 
,)()( Se 2.
).()( temos 
,0 com ,)()( Se 1.
log
log
log
log
log
nfnT
cncfbnafnnf
nnnT
nnf
nnT
nOnf
a
a
a
a
a
b
b
b
b
b
Θ=
<≤>Ω=
Θ=
Θ=
Θ=
>=
+
−
ε
ε
ε
ε
)()/()( nfbnaTnT +=
•  g(n) é O(f(n)): g(n) ≤ cf(n), para todo n ≥ m 
•  g(n) é Ω(f(n)): g(n) ≥ cf(n), para todo n ≥ m 
•  g(n) é Ө(f(n)): 0 ≤ c1f(n) ≤ g(n) ≤ c2f(n), para todo n ≥ m 
Teorema Mestre (2) 
n  Resolva a recorrência 
usando o teorema mestre 
n  Caso 2 se aplica, temos 
132 += )/()( nTnT
))(log(Θ)( nnT =
)).(()( temos 
,1 para )()/( se e 0 para )()( Se 3.
).log()( temos 
,)()( Se 2.
).()( temos 
,0 com ,)()( Se 1.
log
log
log
log
log
nfnT
cncfbnafnnf
nnnT
nnf
nnT
nOnf
a
a
a
a
a
b
b
b
b
b
Θ=
<≤>Ω=
Θ=
Θ=
Θ=
>=
+
−
ε
ε
ε
ε
)()/()( nfbnaTnT +=
•  g(n) é O(f(n)): g(n) ≤ cf(n), para todo n ≥ m 
•  g(n) é Ω(f(n)): g(n) ≥ cf(n), para todo n ≥ m 
•  g(n) é Ө(f(n)): 0 ≤ c1f(n) ≤ g(n) ≤ c2f(n), para todo n ≥ m 
Teorema Mestre (3) 
n  Resolva a recorrência 
usando o teorema mestre 
n  Caso 3 se aplica, temos 
nnnTnT log)4/(3)( +=
)log()( nnnT Θ=
)).(()( temos 
,1 para )()/( se e 0 para )()( Se 3.
).log()( temos 
,)()( Se 2.
).()( temos 
,0 com ,)()( Se 1.
log
log
log
log
log
nfnT
cncfbnafnnf
nnnT
nnf
nnT
nOnf
a
a
a
a
a
b
b
b
b
b
Θ=
<≤>Ω=
Θ=
Θ=
Θ=
>=
+
−
ε
ε
ε
ε
)()/()( nfbnaTnT +=
•  g(n) é O(f(n)): g(n) ≤ cf(n), para todo n ≥ m 
•  g(n) é Ω(f(n)): g(n) ≥ cf(n), para todo n ≥ m 
•  g(n) é Ө(f(n)): 0 ≤ c1f(n) ≤ g(n) ≤ c2f(n), para todo n ≥ m 
Teorema Mestre (4) 
n  Novamente a equação de recorrência: 
T(n) = 2T(n/2) + n; 
T(1) = 1; 
T(n) = 2T(n/2) + n; 
T(1) = 1; 
)).(()( temos 
,1 para )()/( se e 0 para )()( Se 3.
).log()( temos 
,)()( Se 2.
).()( temos 
,0 com ,)()( Se 1.
log
log
log
log
log
nfnT
cncfbnafnnf
nnnT
nnf
nnT
nOnf
a
a
a
a
a
b
b
b
b
b
Θ=
<≤>Ω=
Θ=
Θ=
Θ=
>=
+
−
ε
ε
ε
ε
)()/()( nfbnaTnT +=
•  g(n) é O(f(n)): g(n) ≤ cf(n), para todo n ≥ m 
•  g(n) é Ω(f(n)): g(n) ≥ cf(n), para todo n ≥ m 
•  g(n) é Ө(f(n)): 0 ≤ c1f(n) ≤ g(n) ≤ c2f(n), para todo n ≥ m 
Algoritmos e Estrutura de Dados II 
Teorema Mestre (5) 
n  Resolva a recorrência 
 
n  Nenhum caso do teorema mestre de aplica 
nnnTnT log)/()( += 22
T(n) = 2T(n/2) + n; 
T(1) = 1; 
)).(()( temos 
,1 para )()/( se e 0 para )()( Se 3.
).log()( temos 
,)()( Se 2.
).()( temos 
,0 com ,)()( Se 1.
log
log
log
log
log
nfnT
cncfbnafnnf
nnnT
nnf
nnT
nOnf
a
a
a
a
a
b
b
b
b
b
Θ=
<≤>Ω=
Θ=
Θ=
Θ=
>=
+
−
ε
ε
ε
ε
)()/()( nfbnaTnT +=
•  g(n) é O(f(n)): g(n) ≤ cf(n), para todo n ≥ m 
•  g(n) é Ω(f(n)): g(n) ≥ cf(n), para todo n ≥ m 
•  g(n) é Ө(f(n)): 0 ≤ c1f(n) ≤ g(n) ≤ c2f(n), para todo n ≥ m

Outros materiais