Na análise de algoritmos, o teorema mestre para recorrências de divisão e conquista fornece uma análise assintótica (usando a notação Grande-O) para relações de recorrência que ocorrem na análise de muitos algoritmos de divisão e conquista. A abordagem foi apresentada pela primeira vez por Jon Bentley, Dorothea Haken, e James B. Saxe , em 1980, onde foi descrito como um "método unificador" para a solução de tais recorrências. O nome "teorema mestre" foi popularizado pelo livro de algoritmos amplamente utilizado Algoritmos: teoria e prática por Cormen, Leiserson, Rivest e Stein.
Nem todas as relações de recorrência podem ser resolvidas com o uso do teorema; suas generalizações incluem o método de Akra-Bazzi.
Introdução Considere um problema que pode ser resolvido usando um algoritmo recursivo como o algoritmo a seguir: procedimento p(entrada x de tamanho n): se n < alguma constante k: Resolver x diretamente, sem recursão senão: Criar a subproblemas de x, cada um com tamanho n/b Chamar o procedimento p recursivamente em cada subproblema Combinar os resultados dos subproblemas O algoritmo acima divide o problema em um número de subproblemas recursivamente, cada subproblema sendo de tamanho . A sua árvore de chamadas tem um nó para cada chamada recursiva, com os filhos do nó sendo as outras chamadas feitas a partir dessa chamada. As folhas da árvore são os casos base da recursão, os subproblemas (de tamanho menor do que k) que não se resolve recursivamente. O exemplo acima teria nós-filhos em cada nó que não fosse uma folha. Cada nó realiza uma quantidade de trabalho que corresponde ao tamanho do sub problema n passado para essa instância da chamada recursiva e dada por . A quantidade total de trabalho realizado pelo algoritmo completo é a soma do trabalho realizado por todos os nós na árvore.O tempo de execução de um algoritmo, como o 'p' acima em uma entrada de tamanho 'n', geralmente denotado por , pode ser expresso pela relação de recorrência
onde é o tempo para criar os subproblemas e combinar seus resultados no procedimento acima. Essa equação pode ser substituída, sucessivamente, por si mesma e se expandir para obter uma expressão para a quantidade total de trabalho realizado.Duke University, "Big-Oh for Recursive Functions: Recurrence Relations", http://www.cs.duke.edu/~ola/ap/recurrence.html O teorema mestre permite que muitas relações de recorrência desta forma serem convertidas para notação teta diretamente, sem fazer uma expansão da relação recursiva. Forma genérica O teorema mestre às vezes produz limites assintoticamente rígidos para algumas recorrências de algoritmos de divisão e conquista,que dividem uma entrada em subproblemas menores de tamanhos iguais, resolvem os subproblemas recursivamente e combinam as soluções dos subproblemas para fornecer uma solução para o problema original. O tempo para tal algoritmo pode ser expresso adicionando o tempo de execução no nível superior de sua recursão (para dividir os problemas em subproblemas e depois combinar as soluções de subproblemas) junto com o tempo de execução nas chamadas recursivas do algoritmo. Se denota o tempo total para o algoritmo em uma entrada de tamanho e indica a quantidade de tempo gasto no nível superior da recorrência, então o tempo pode ser expresso por uma relação de recorrência que assume a forma:
Aqui é o tamanho da entrada de um problema, é o número de subproblemas na recursão, e é o fator pelo qual o tamanho do subproblema é reduzido em cada chamada recursiva (por exemplo, se o valor for 2, então o subproblema terá metade do tamanho). O teorema abaixo também assume um caso base para a recorrência, quando é menor que algum limite .
Recorrências desta forma frequentemente satisfazem um dos três casos a seguir, baseado em como o trabalho para dividir/recombinar o problema relaciona-se com a expoente crítico. (A tabela abaixo utiliza o padrão de big O notation.)
CasoDescriçãoCondição sobre em relação a , i.e. Limite do Teorema MestreExemplos notacionais1O trabalho para dividir/recombinar um problema é reduzido pelos subproblemas.
i.e. a árvore de recursão é leaf-heavyQuando onde
(limitado superiormente por um polinômio de expoente menor)... então
(O termo de divisão não aparece; a estrutura da árvore recursiva domina.)Se e , então .2O trabalho para dividir/recombinar um problema é comparável aos subproblemas.Quando para qualquer
(faixa limitada pelo polinômio de expoente crítico, vezes zero ou mais opcional s)... então
(O limite é o termo de divisão, em que o log é aumentado por uma única potência.)Se e , então .
Se e , então .3O trabalho para dividir/recombinar um problema domina os subproblemas.
i.e. a árvore de recursão é root-heavy.Quando onde
(limitado inferiormente por um polinômio de maior expoente)... isso não produz necessariamente nada. Se é sabido ainda que
para alguma constante e suficientemente grande (frequentemente chamado de condição de regularidade)
então o total é dominado pelo termo de divisão :
Se e e a condição de regularidade é satisfeita, então . Uma extensão útil do caso 2 abrange todos os valores de Chee Yap, A real elementary approach to the master recurrence and generalizations, Proceedings of the 8th annual conference on Theory and applications of models of computation (TAMC'11), pages 14–26, 2011. Online copy. Caso , i.e. Limite do teorema mestreExemplos notacionais2aQuando para qualquer ... então
(O limite é o termo de divisão, em que o log é aumentado por uma única potência.) e, então.2bQuando para ... então
(O limite é o termo de divisão, em que o log recíproco é substituído por um log iterado.)Se , então .2cQuando para qualquer ... então
(O limite é o termo de divisão, onde o log desaparece.)Se e, então .
Exemplos
Exemplo do caso 1
Como se pode ver a partir da fórmula acima:
, então , onde
Em seguida, vamos ver se conseguimos satisfazer a condição do caso 1:
.
Do primeiro caso do teorema mestre, segue que
(de fato, a solução exata da relação de recorrência é , assumindo ).
Exemplo do caso 2
Como podemos ver na fórmula acima as variáveis possuem os seguintes valores:
onde
Em seguida, vamos ver se conseguimos satisfazer a condição do caso 2:
e, portanto,
Do segundo caso do teorema mestre, segue que
Assim, a relação de recorrência está em .
(Este resultado é confirmado pela solução exata da relação de recorrência, que é , assumindo .)
Exemplo do caso 3
Como podemos ver na fórmula acima as variáveis possuem os seguintes valores:
, onde
Em seguida, vamos ver se a condição do caso 3 é satisfeita: , e portanto, sim,
A condição de regularidade também é satisfeita:
, escolhendo
Então, pelo terceiro caso do teorema mestre:
Assim, a relação de recorrência está em , que está em conformidade com o da fórmula original.
(Esse resultado é confirmado pela solução exata da relação de recorrência, que é , assumindo .)
Equações inadmissíveis As equações a seguir não podem ser resolvidas utilizando o teorema mestre:Massachusetts Institute of Technology (MIT), "Master Theorem: Practice Problems and Solutions", http://www.csail.mit.edu/~thies/6.046-web/master.pdf, Arquivado em http://web.archive.org/web/20110809082605/http://people.csail.mit.edu/thies/6.046-web/master.pdf
não é uma constante; o número de subproblemas deveria ser fixo
diferença não polinomial entre f(n) e (veja abaixo; a versão estendida se aplica)
não pode haver menos que um subproblema
f(n), que é o tempo de combinação (dos subproblema), não é positivo
caso 3, mas viola a condição de regularidade.
No segundo exemplo inadmissível acima, a diferença entre e pode ser expressa com a relação . É claro que para qualquer constante . Portanto, a diferença não é polinomial e a forma básica do Teorema Mestre não se aplica. A forma estendida (caso 2b) aplica-se, dando a solução .
Aplicação em algoritmos comuns AlgortimoRelação de recorrênciaTempo de execuçãoComentárioPesquisa bináriaAplicado o caso do teorema mestre , onde Dartmouth College, http://www.math.dartmouth.edu/archive/m19w03/public_html/Section5-2.pdfPercurso em árvore bináriaAplicado o caso do teorema mestre ondePesquisa ótima de matriz ordenadaAplica o caso do método de Akra-Bazzi para e Merge sortAplica o caso do teorema mestre , onde
Ver também Método de Akra-Bazzi Complexidade assintótica
Notas
Referências
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introdução a Algoritmos, Segunda Edição. MIT Press e McGraw–Hill, 2001. . Seções 4.3 (O teorema mestre) e 4.4 (Prova do teorema mestre), pp. 73–90. Michael T. Goodrich e Roberto Tamassia. Algorithm Design: Foundation, Analysis, and Internet Examples. Wiley, 2002. . O teorema mestre (incluindo a versão de Caso 2 incluídos aqui, que é mais forte do que o do CLRS) está no pp. 268-270.
Ligações externas Teorema Mestre e Exemplos Resolvidos Exercícios resolvidos sobre o teorema mestre
Categoria:Teoremas em matemática discreta Categoria:Análise de algoritmos Categoria:Complexidade de algoritmos Categoria:Análise assintótica Categoria:Relações de recorrência