aula09 TeoremaMestre

Prévia do material em texto

Projeto e Análise de Algoritmos
Recorrências
Teorema Mestre
Prof. Humberto Brandão
humberto@dcc.ufmg.br
Universidade Federal de Alfenas
Laboratório de Pesquisa e Desenvolvimento (LP&D)
Instituto de Ciências Exatas (ICEx)
versão da aula: 0.3
Última aula...
• Recorrências...
1)1(
2)1()2(
...
4)4()3(
3)3()2(
2)2()1(
1)1()(






nT
nTT
nTnT
nTnT
nTnT
nTnT
)(
2
)(
2
)(
2
2
2
)(
2
)1(
)(
)1()2(...4321)(
2
2
2
22
1
1
1
n
nn
nT
nn
nT
nnn
n
nn
nT
n
nn
niinT
nnnT
n
i
n
i














 












Métodos gerais para resolver 
recorrências
Método de substituição
Método de Árvore de Recursão
Teorema Mestre
Método geral para resolver 
recorrências
• Método da Substituição: estabelecemos um limite hipotético e 
depois empregamos a indução matemática para provar que nossa 
suposição era correta.
Método geral para resolver 
recorrências
• Método da Substituição: estabelecemos um limite hipotético e 
depois empregamos a indução matemática para provar que nossa 
suposição era correta.
• Método de Árvore de Recursão: converte a recorrência em uma 
árvore cujos nós representam os custos envolvidos em diversos 
níveis da recursão.
• Mais detalhes em Cormen (2002).
Método geral para resolver 
recorrências
• Teorema mestre:
– O teorema mestre fornece um “livro de receitas” para 
resolver algumas equações de recorrência.
Método geral para resolver 
recorrências
• Teorema mestre:
– O teorema mestre fornece um “livro de receitas” para 
resolver algumas equações de recorrência.
– Resolve recorrências no formato
• onde a >= 1 e b > 1 são constantes e f(n) é uma função 
assintoticamente positiva podem ser resolvidas usando o 
Teorema Mestre. 
  f(n)n/baTT(n) 
Método geral para resolver 
recorrências
• Teorema mestre:
  f(n)n/baTT(n) 
Método geral para resolver 
recorrências
• Teorema mestre:
• Se para alguma constante  > 0, então
  f(n)n/baTT(n) 
  abnnf log)(
)()(
log abnnT 
  abnnf log)(
)()(
log abnnT 
Método geral para resolver 
recorrências
• Teorema mestre:
• Se para alguma constante  > 0, então
• Se então
  f(n)n/baTT(n) 
  abnnf log)(
)()(
log abnnT 
 abnnf log)( 
)log()(
log
nnnT
ab
  abnnf log)(
)()(
log abnnT 
 abnnf log)( 
)log()(
log
nnnT
ab
Método geral para resolver 
recorrências
• Teorema mestre:
• Se para alguma constante  > 0, então
• Se então
• Se para alguma constante  > 0, 
e se para alguma constante c < 1 e para todo n
suficientemente grande, então 
  f(n)n/baTT(n) 
  abnnf log)(
)()(
log abnnT 
 abnnf log)( 
)log()(
log
nnnT
ab
  abnnf log)(
)()/( ncfbnaf 
))(()( nfnT 
  abnnf log)(
)()(
log abnnT 
 abnnf log)( 
)log()(
log
nnnT
ab
Método geral para resolver 
recorrências
• Teorema mestre:
– Exemplo 01
– Qual caso do Teorema mestre?
  f(n)n/baTT(n) 
 
nnf
b
a
nnTT(n)




)(
3
9
3/9
Método geral para resolver 
recorrências
• Teorema mestre:
– Exemplo 01
• Aplicando o caso 1 do teorema mestre:
– Se para alguma constante  > 0, então
  f(n)n/baTT(n) 
 
nnf
b
a
nnTT(n)




)(
3
9
3/9
  abnnf log)(
)()(
log abnnT 
Método geral para resolver 
recorrências
• Teorema mestre:
– Exemplo 01
• Aplicando o caso 1 do teorema mestre:
– Se para alguma constante  > 0, então
  f(n)n/baTT(n) 
 
nnf
b
a
nnTT(n)




)(
3
9
3/9
  abnnf log)(
)()(
log abnnT 
 
)()( 2
999,1
nnT
nn


Método geral para resolver 
recorrências
• Teorema mestre:
– Exemplo 02
– Qual caso do Teorema mestre?
  f(n)n/baTT(n) 
 
nnf
b
a
nnTT(n)




)(
4
2
4/2
Método geral para resolver 
recorrências
• Teorema mestre:
– Exemplo 02
• Aplicando o caso 2 do teorema mestre:
– Se então
  f(n)n/baTT(n) 
 abnnf log)( 
)log()(
log
nnnT
ab
 
nnf
b
a
nnTT(n)




)(
4
2
4/2
Método geral para resolver 
recorrências
• Teorema mestre:
– Exemplo 02
• Aplicando o caso 2 do teorema mestre:
– Se então
  f(n)n/baTT(n) 
 abnnf log)( 
)log()(
log
nnnT
ab
   2/12log4 nnn 
)log()( nnnT 
 
nnf
b
a
nnTT(n)




)(
4
2
4/2
Método geral para resolver 
recorrências
• Teorema mestre:
– Exemplo 03
– Qual caso do Teorema mestre?
 
nnnf
b
a
nnnTT(n)
log)(
4
3
log4/3




Método geral para resolver 
recorrências
• Teorema mestre:
– Exemplo 03
• Aplicando o caso 3 do teorema mestre:
– Se para alguma constante  > 0, 
e se para alguma constante c < 1 e para todo n
suficientemente grande, então
 
nnnf
b
a
nnnTT(n)
log)(
4
3
log4/3




  abnnf log)(
)()/( ncfbnaf 
))(()( nfnT 
  )(log 7925,0log nnnn ab  
Método geral para resolver 
recorrências
• Aplicando o caso 3 do teorema mestre:
– Precisamos mostrar também que a condição de regularidade é 
válida para f(n).
– ...e se para alguma constante c < 1 e para todo 
n suficientemente grande, então
)()/( ncfbnaf 
))(()( nfnT 
 
 
4/3
log2log
4
3
log
4
3
4loglog
4
3
log
4
3
)4/log()4/(3
)()4/(3
)()/(






cpara
ncnnn
nnn
n
nnnn
ncfnf
ncfbnaf  
nnnf
b
a
nnnTT(n)
log)(
4
3
log4/3




)log()(
Portanto,
nnnT 
Exercícios
• No site!!!
Bibliografia
• CORMEN, T. H.; LEISERSON, C. E.; RIVEST, R. L.; (2002). 
Algoritmos – Teoria e Prática. Tradução da 2ª edição americana. 
Rio de Janeiro. Editora Campus.
• TAMASSIA, ROBERTO; GOODRICH, MICHAEL T. (2004). 
Projeto de Algoritmos - Fundamentos, Análise e Exemplos da 
Internet.