Mostrar código-fonte de Teorema mestre (análise de algoritmos)

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 algoritmos|análise]] de muitos [[Divisão e conquista|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.<ref>{{citation|title=A general method for solving divide-and-conquer recurrences|author3-link=James B. Saxe|pages=36–44|issue=3|volume=12|journal=[[ACM SIGACT News]]|url=http://www.dtic.mil/get-tr-doc/pdf?AD=ADA064294|date=Setembro de 1980|author2-link=Dorothea Blostein|last1=Bentley|author1-link=Jon Bentley (computer scientist)|first3=James B.|first2=Dorothea|first1=Jon Louis|last3=Saxe|last2=Haken|doi=10.1145/1008861.1008865}}</ref> O nome "teorema mestre" foi popularizado pelo livro de algoritmos amplamente utilizado A''lgoritmos: teoria e prática'' por Cormen, [[Charles Eric Leiserson|Leiserson]], [[Ronald Rivest|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|método de Akra-Bazzi]].

== Introdução ==
Considere um problema que pode ser resolvido usando um [[Recursividade (ciência da computação)|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 {{Math|''n''/''b''}}. 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 <math>a</math> 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 <math>f(n)</math>. A quantidade total de trabalho realizado pelo algoritmo completo é a soma do trabalho realizado por todos os nós na árvore.<math /><math /><math />O tempo de execução de um algoritmo, como o 'p' acima em uma entrada de tamanho 'n', geralmente denotado por <math>T(n)</math>, pode ser expresso pela [[relação de recorrência]]

<math>T(n)=aT(\frac{n}{b})+f(n)</math>

onde <math>f(n)</math> é 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.<ref>Duke University,
    "Big-Oh for Recursive Functions: Recurrence Relations",
    http://www.cs.duke.edu/~ola/ap/recurrence.html
</ref> O teorema mestre permite que muitas relações de recorrência desta forma serem convertidas para [[Grande-O|notação teta]] diretamente, sem fazer uma expansão da relação recursiva.<math />
== Forma genérica ==
<math /><math /><math /><math />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:

<math>T(n)=aT(\frac{n}{b})+f(n)</math><math /><math /><math /><math /><math /><math />Aqui <math>n</math> é o tamanho da entrada de um problema, <math>a</math> é o número de subproblemas na recursão, e <math>b</math> é 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, <math>T(n)=\Theta(1)</math> quando <math>n</math> é menor que algum limite <math>\kappa > 0</math>.

Recorrências desta forma frequentemente satisfazem um dos três casos a seguir, baseado em como o trabalho para dividir/recombinar o problema <math>f(n)</math> relaciona-se com a ''expoente crítico''. (A tabela abaixo utiliza o padrão de [[Grande-O|big O notation]].)<math /><math />

:<math>c_{\operatorname{crit}} = \log_b a = \log(\#\text{subproblemas})/\log(\text{tamanho relativo do subproblema})</math>

{| class="wikitable" style="margin-bottom: 10px;"
! width="10" |Caso
!Descrição
!Condição sobre <math>f(n)</math> em relação a <math>c_{\operatorname{crit}}</math>, i.e. <math>\log_b a</math>
!Limite do Teorema Mestre
! width="400" |Exemplos notacionais
|-
!1
|O trabalho para dividir/recombinar um problema é reduzido pelos subproblemas.

i.e. a árvore de recursão é leaf-heavy
|Quando <math>f(n) = O(n^{c})</math> onde <math>c<c_{\operatorname{crit}}</math> 

(limitado superiormente por um polinômio de expoente menor)
|... então <math>T(n)= \Theta\left( n^{c_{\operatorname{crit}}} \right)</math>

(O termo de divisão não aparece; a estrutura da árvore recursiva domina.)
|Se <math>b=a^2</math> and <math>f(n) = O(n^{1/2-\epsilon})</math>, então <math>T(n) = \Theta(n^{1/2})</math>.
|-
!2
|O trabalho para dividir/recombinar um problema é comparável aos subproblemas.
|Quando <math>f(n) = \Theta(n^{c_{\operatorname{crit}}}\log^{k} n)</math> para qualquer <math>k \ge 0</math>

(faixa limitada pelo polinômio de expoente crítico, vezes zero ou mais opcional <math>\log</math>s)
|... então <math>T(n)= \Theta\left( n^{c_{\operatorname{crit}}} \log^{k+1} n \right)</math>

(O limite é o termo de divisão, em que o log é aumentado por uma única potência.)
|Se <math>b=a^2</math> e <math>f(n) = \Theta(n^{1/2})</math>, então <math>T(n) = \Theta(n^{1/2} \log n)</math>.

Se <math>b=a^2</math> e <math>f(n) = \Theta(n^{1/2} \log n)</math>, então <math>T(n) = \Theta(n^{1/2} \log^{2} n)</math>.
|-
!3
|O trabalho para dividir/recombinar um problema domina os subproblemas.

i.e. a árvore de recursão é ''root-heavy''.
|Quando <math>f(n) = \Omega(n^{c})</math>onde <math>c>c_{\operatorname{crit}}</math> 

(limitado inferiormente por um polinômio de maior expoente)
|... isso não produz necessariamente nada. Se é sabido ainda que

: <math>a f\left( \frac{n}{b} \right) \le k f(n)</math> para alguma constante <math>k < 1</math> e suficientemente grande <math>n</math> (frequentemente chamado de ''condição de regularidade'')

então o total é dominado pelo termo de divisão <math>f(n)</math>:

: <math>T\left(n \right) = \Theta\left(f(n) \right)</math>
|Se <math>b=a^2</math> e <math>f(n) = \Omega(n^{1/2+\epsilon})</math> e a condição de regularidade é satisfeita, então <math>T(n) = \Theta(f(n))</math>.
|}
Uma extensão útil do caso 2 abrange todos os valores de <math>k</math><ref name="Yap">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. [https://pdfs.semanticscholar.org/5273/51a915d7f34f8965c74ecf422e70cd410b52.pdf Online copy.]
</ref>
{| class="wikitable" style="margin-bottom: 34px;"
! width="10" |Caso
!<math>f(n)</math> <math>c_{\operatorname{crit}}</math>, i.e. <math>\log_b a</math>
!Limite do teorema mestre
! width="400" |Exemplos notacionais
|-
!2a
|Quando <math>f(n) = \Theta(n^{c_{\operatorname{crit}}}\log^{k} n)</math> para qualquer <math>k > -1</math>
|... então<math>T(n)= \Theta\left( n^{c_{\operatorname{crit}}} \log^{k+1} n \right)</math>

(O limite é o termo de divisão, em que o log é aumentado por uma única potência.)
|<math>b=a^2</math> e<math>f(n) = \Theta(n^{1/2}/\log^{1/2} n)</math>, então<math>T(n) = \Theta(n^{1/2} \log^{1/2} n)</math>.
|-
!2b
|Quando <math>f(n) = \Theta(n^{c_{\operatorname{crit}}}\log^{k} n)</math> fpara <math>k = -1</math>
|... then <math>T(n)= \Theta\left( n^{c_{\operatorname{crit}}} \log \log n \right)</math>

(O limite é o termo de divisão, em que o log recíproco é substituído por um log iterado.)
|Se <math>b=a^2</math> <math>f(n) = \Theta(n^{1/2}/\log n)</math>, então <math>T(n) = \Theta(n^{1/2} \log \log n)</math>.
|-
!2c
|Quando<math>f(n) = \Theta(n^{c_{\operatorname{crit}}}\log^{k} n)</math> para qualquer <math>k < -1</math>
|... then <math>T(n)= \Theta\left( n^{c_{\operatorname{crit}}} \right)</math>

(O limite é o termo de divisão, onde o log desaparece.)
|Se <math>b=a^2</math> e<math>f(n) = \Theta(n^{1/2}/\log^2 n)</math>, então <math>T(n) = \Theta(n^{1/2})</math>.
|}

=== Exemplos ===

==== Exemplo do caso 1 ====

:<math>T(n) = 8 T\left(\frac{n}{2}\right) + 1000n^2</math>

Como se pode ver a partir da fórmula acima:

:<math>a = 8, \, b = 2, \, f(n) = 1000n^2</math>, então
:<math>f(n) = O\left(n^c\right)</math>, onde <math>c = 2</math>

Em seguida, vamos ver se conseguimos satisfazer a condição do caso 1:

:<math>\log_b a = \log_2 8 = 3>c</math>.

Do primeiro caso do teorema mestre, segue que

:<math>T(n) = \Theta\left( n^{\log_b a} \right) = \Theta\left( n^{3} \right)</math>

(de fato, a solução exata da relação de recorrência é <math>T(n) = 1001 n^3 - 1000 n^2</math>, assumindo <math>T(1) = 1</math>).

==== Exemplo do caso 2 ====
<math>T(n) = 2 T\left(\frac{n}{2}\right) + 10n</math>

Como podemos ver na fórmula acima as variáveis possuem os seguintes valores:

:<math>a = 2, \, b = 2, \, c = 1, \, f(n) = 10n</math>
:<math>f(n) = \Theta\left(n^{c} \log^{k} n\right)</math> onde <math>c = 1, k = 0</math>

Em seguida, vamos ver se conseguimos satisfazer a condição do caso 2:

:<math>\log_b a = \log_2 2 = 1</math> e, portanto, <math>c = \log_b a</math>

Do segundo caso do teorema mestre, segue que

:<math>T(n) = \Theta\left( n^{\log_b a} \log^{k+1} n\right) = \Theta\left( n^{1} \log^{1} n\right) = \Theta\left(n \log n\right)</math> 

Assim, a relação de recorrência <math>T(n)</math> está em <math>\Theta(n\log n)</math>.

(Este resultado é confirmado pela solução exata da relação de recorrência, que é <math>T(n) = n + 10 n\log_2 n</math>, assumindo <math>T(1) = 1</math>.)

==== Exemplo do caso 3 ====
:<math>T(n) = 2 T\left(\frac{n}{2}\right) + n^2</math>

Como podemos ver na fórmula acima as variáveis possuem os seguintes valores:

:<math>a = 2, \, b = 2, \, f(n) = n^2</math>
:<math>f(n) = \Omega\left(n^c\right)</math>, onde <math>c = 2</math>

Em seguida, vamos ver se a condição do caso 3 é satisfeita:
:<math>\log_b a = \log_2 2 = 1</math>, e portanto, sim, <math>c > \log_b a</math>

A condição de regularidade  também é satisfeita:

:<math> 2 \left(\frac{n^2}{4}\right) \le k n^2 </math>, escolhendo <math> k = 1/2 </math>

Então, pelo terceiro caso do teorema mestre:

:<math>T \left(n \right) = \Theta\left(f(n)\right) = \Theta \left(n^2 \right).</math>

Assim, a relação de recorrência <math>T(n)</math> está em <math>\Theta(n^2)</math>, que está em conformidade com o <math>f(n)</math> da fórmula original.

(Esse resultado é confirmado pela solução exata da relação de recorrência, que é <math>T(n) = 2 n^2 - n</math>, assumindo <math>T(1) = 1</math>.)

== Equações inadmissíveis ==
As equações a seguir não podem ser resolvidas utilizando o teorema mestre:<ref>
Massachusetts Institute of Technology (MIT), "Master Theorem: Practice Problems and Solutions", http://www.csail.mit.edu/~thies/6.046-web/master.pdf{{Ligação inativa|1={{subst:DATA}} }}, Arquivado em http://web.archive.org/web/20110809082605/http://people.csail.mit.edu/thies/6.046-web/master.pdf
</ref>

* <math>T(n) = 2^nT\left (\frac{n}{2}\right )+n^n</math>
*: <math>a</math> não é uma constante; o número de subproblemas deveria ser fixo
* <math>T(n) = 2T\left (\frac{n}{2}\right )+\frac{n}{\log n}</math>
*: diferença não polinomial entre f(n) e <math>n^{\log_b a}</math> (veja abaixo; a versão estendida se aplica)
* <math>T(n) = 0.5T\left (\frac{n}{2}\right )+n</math>
*: <math> a<1 </math> não pode haver menos que um subproblema
* <math>T(n) = 64T\left (\frac{n}{8}\right )-n^2\log n</math>
*: f(n), que é o tempo de combinação (dos subproblema), não é positivo
* <math>T(n) = T\left (\frac{n}{2}\right )+n(2-\cos n)</math>
*: caso 3, mas viola a condição de regularidade.

No segundo exemplo inadmissível acima, a diferença entre <math>f(n)</math> e <math>n^{\log_b a}</math> pode ser expressa com a relação <math>\frac{f(n)}{n^{\log_b a}} = \frac{n / \log n}{n^{\log_2 2}} = \frac{n}{n \log n} = \frac{1}{\log n}</math>. É claro que <math>\frac{1}{\log n} < n^\epsilon</math> para qualquer constante <math>\epsilon > 0</math>. 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 <math>T(n) = \Theta(n\log\log n)</math>.

== Aplicação em algoritmos comuns ==
{| class="wikitable" style="margin-bottom: 10px;"
!Algortimo
!Relação de recorrência
!Tempo de execução
!Comentário
|-
|[[Pesquisa binária]]
|<math>T(n) = T\left(\frac{n}{2}\right) + O(1)</math>
|<math>O(\log n)</math>
|Aplicado o caso do teorema mestre <math>c = \log_b a</math>, onde <math>a = 1, b = 2, c = 0, k = 0</math><ref name="dartmouth">Dartmouth College,
    http://www.math.dartmouth.edu/archive/m19w03/public_html/Section5-2.pdf
</ref>
|-
|Percurso em árvore binária
|<math>T(n) = 2 T\left(\frac{n}{2}\right) + O(1)</math>
|<math>O(n)</math>
|Aplicado o caso do teorema mestre <math>c < \log_b a</math> onde<math>a = 2, b = 2, c = 0</math>
|-
|Pesquisa ótima de matriz ordenada
|<math>T(n) = 2 T\left(\frac{n}{2}\right) + O(\log n)</math>
|<math>O(n)</math>
|Aplica o caso do [[Método de Akra–Bazzi|método de Akra-Bazzi]] para <math>p=1</math> e <math>g(u)=\log(u)</math> <math>\Theta(2n - \log n)</math>
|-
|[[Merge sort]]
|<math>T(n) = 2 T\left(\frac{n}{2}\right) + O(n)</math>
|<math>O(n \log n)</math>
|Aplica o caso do teorema mestre <math>c = \log_b a</math>, onde <math>a = 2, b = 2, c = 1, k = 0</math>
|}

== Ver também ==
* [[Método de Akra–Bazzi|Método de Akra-Bazzi]]
* [[Complexidade computacional|Complexidade assintótica]]

== Notas ==
{{reflist}}

== Referências ==

* Thomas H. Cormen, [[Charles Eric Leiserson|Charles E. Leiserson]], [[Ronald Rivest|Ronald L. Rivest]], Clifford Stein. ''Introdução a Algoritmos'', Segunda Edição. [[Instituto de Tecnologia de Massachusetts|MIT Press]] e McGraw–Hill, 2001. {{ISBN|0-262-03293-7}}. Seções 4.3 (O teorema mestre) e 4.4 (Prova do teorema mestre), pp. &#x20;73&#x2013;90.
* Michael T. Goodrich e Roberto Tamassia. ''Algorithm Design: Foundation, Analysis, and Internet Examples''. Wiley, 2002. {{ISBN|0-471-38365-1}}. O teorema mestre (incluindo a versão de Caso 2 incluídos aqui, que é mais forte do que o do CLRS) está no pp. &#x20;268-270.

== Ligações externas ==
* [https://www.blogcyberini.com/2017/11/teorema-mestre.html Teorema Mestre e Exemplos Resolvidos]
*[https://www.blogcyberini.com/2017/12/exercicios-resolvidos-teorema-mestre.html Exercícios resolvidos sobre o teorema mestre]

{{DEFAULTSORT: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]]