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 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 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 $a$ 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 $f(n)$. A quantidade total de trabalho realizado pelo algoritmo completo é a soma do trabalho realizado por todos os nós na árvore.${\displaystyle }$${\displaystyle }$${\displaystyle }$O tempo de execução de um algoritmo, como o 'p' acima em uma entrada de tamanho 'n', geralmente denotado por $T(n)$, pode ser expresso pela relação de recorrência

$T(n)=aT({\frac {n}{b}})+f(n)$

onde $f(n)$ é 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. 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.${\displaystyle }$

Forma genérica

${\displaystyle }$${\displaystyle }$${\displaystyle }$${\displaystyle }$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:

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

Recorrências desta forma frequentemente satisfazem um dos três casos a seguir, baseado em como o trabalho para dividir/recombinar o problema $f(n)$ relaciona-se com a expoente crítico. (A tabela abaixo utiliza o padrão de big O notation.)${\displaystyle }$${\displaystyle }$

$c_{\operatorname {crit} }=\log _{b}a=\log(\#{\text{subproblemas}})/\log({\text{tamanho relativo do subproblema}})$

Caso	Descrição	Condição sobre $f(n)$ em relação a $c_{\operatorname {crit} }$, i.e. $\log _{b}a$	Limite do Teorema Mestre	Exemplos notacionais
1	O trabalho para dividir/recombinar um problema é reduzido pelos subproblemas. i.e. a árvore de recursão é leaf-heavy	Quando $f(n)=O(n^{c})$ onde $c<c_{\operatorname {crit} }$ (limitado superiormente por um polinômio de expoente menor)	... então $T(n)=\Theta \left(n^{c_{\operatorname {crit} }}\right)$ (O termo de divisão não aparece; a estrutura da árvore recursiva domina.)	Se $b=a^{2}$ and $f(n)=O(n^{1/2-\epsilon })$, então $T(n)=\Theta (n^{1/2})$.
2	O trabalho para dividir/recombinar um problema é comparável aos subproblemas.	Quando $f(n)=\Theta (n^{c_{\operatorname {crit} }}\log ^{k}n)$ para qualquer $k\geq 0$ (faixa limitada pelo polinômio de expoente crítico, vezes zero ou mais opcional $\log$s)	... então $T(n)=\Theta \left(n^{c_{\operatorname {crit} }}\log ^{k+1}n\right)$ (O limite é o termo de divisão, em que o log é aumentado por uma única potência.)	Se $b=a^{2}$ e $f(n)=\Theta (n^{1/2})$, então $T(n)=\Theta (n^{1/2}\log n)$. Se $b=a^{2}$ e $f(n)=\Theta (n^{1/2}\log n)$, então $T(n)=\Theta (n^{1/2}\log ^{2}n)$.
3	O trabalho para dividir/recombinar um problema domina os subproblemas. i.e. a árvore de recursão é root-heavy.	Quando $f(n)=\Omega (n^{c})$onde $c>c_{\operatorname {crit} }$ (limitado inferiormente por um polinômio de maior expoente)	... isso não produz necessariamente nada. Se é sabido ainda que $af\left({\frac {n}{b}}\right)\leq kf(n)$ para alguma constante $k<1$ e suficientemente grande $n$ (frequentemente chamado de condição de regularidade) então o total é dominado pelo termo de divisão $f(n)$: $T\left(n\right)=\Theta \left(f(n)\right)$	Se $b=a^{2}$ e $f(n)=\Omega (n^{1/2+\epsilon })$ e a condição de regularidade é satisfeita, então $T(n)=\Theta (f(n))$.

Uma extensão útil do caso 2 abrange todos os valores de $k$

Caso	$f(n)$ $c_{\operatorname {crit} }$, i.e. $\log _{b}a$	Limite do teorema mestre	Exemplos notacionais
2a	Quando $f(n)=\Theta (n^{c_{\operatorname {crit} }}\log ^{k}n)$ para qualquer $k>-1$	... então$T(n)=\Theta \left(n^{c_{\operatorname {crit} }}\log ^{k+1}n\right)$ (O limite é o termo de divisão, em que o log é aumentado por uma única potência.)	$b=a^{2}$ e$f(n)=\Theta (n^{1/2}/\log ^{1/2}n)$, então$T(n)=\Theta (n^{1/2}\log ^{1/2}n)$.
2b	Quando $f(n)=\Theta (n^{c_{\operatorname {crit} }}\log ^{k}n)$ fpara $k=-1$	... then $T(n)=\Theta \left(n^{c_{\operatorname {crit} }}\log \log n\right)$ (O limite é o termo de divisão, em que o log recíproco é substituído por um log iterado.)	Se $b=a^{2}$ $f(n)=\Theta (n^{1/2}/\log n)$, então $T(n)=\Theta (n^{1/2}\log \log n)$.
2c	Quando$f(n)=\Theta (n^{c_{\operatorname {crit} }}\log ^{k}n)$ para qualquer $k<-1$	... then $T(n)=\Theta \left(n^{c_{\operatorname {crit} }}\right)$ (O limite é o termo de divisão, onde o log desaparece.)	Se $b=a^{2}$ e$f(n)=\Theta (n^{1/2}/\log ^{2}n)$, então $T(n)=\Theta (n^{1/2})$.

Exemplos

Exemplo do caso 1

$T(n)=8T\left({\frac {n}{2}}\right)+1000n^{2}$

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

$a=8,\,b=2,\,f(n)=1000n^{2}$, então

$f(n)=O\left(n^{c}\right)$, onde $c=2$

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

$\log _{b}a=\log _{2}8=3>c$.

Do primeiro caso do teorema mestre, segue que

$T(n)=\Theta \left(n^{\log _{b}a}\right)=\Theta \left(n^{3}\right)$

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

Exemplo do caso 2

$T(n)=2T\left({\frac {n}{2}}\right)+10n$

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

$a=2,\,b=2,\,c=1,\,f(n)=10n$

$f(n)=\Theta \left(n^{c}\log ^{k}n\right)$ onde $c=1,k=0$

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

$\log _{b}a=\log _{2}2=1$ e, portanto, $c=\log _{b}a$

Do segundo caso do teorema mestre, segue que

$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)$

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

(Este resultado é confirmado pela solução exata da relação de recorrência, que é $T(n)=n+10n\log _{2}n$, assumindo $T(1)=1$.)

Exemplo do caso 3

$T(n)=2T\left({\frac {n}{2}}\right)+n^{2}$

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

$a=2,\,b=2,\,f(n)=n^{2}$

$f(n)=\Omega \left(n^{c}\right)$, onde $c=2$

Em seguida, vamos ver se a condição do caso 3 é satisfeita:

$\log _{b}a=\log _{2}2=1$, e portanto, sim, $c>\log _{b}a$

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

$2\left({\frac {n^{2}}{4}}\right)\leq kn^{2}$, escolhendo $k=1/2$

Então, pelo terceiro caso do teorema mestre:

$T\left(n\right)=\Theta \left(f(n)\right)=\Theta \left(n^{2}\right).$

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

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

Equações inadmissíveis

As equações a seguir não podem ser resolvidas utilizando o teorema mestre:

• $T(n)=2^{n}T\left({\frac {n}{2}}\right)+n^{n}$

  $a$ não é uma constante; o número de subproblemas deveria ser fixo

• $T(n)=2T\left({\frac {n}{2}}\right)+{\frac {n}{\log n}}$

  diferença não polinomial entre f(n) e $n^{\log _{b}a}$ (veja abaixo; a versão estendida se aplica)

• $T(n)=0.5T\left({\frac {n}{2}}\right)+n$

  $a<1$ não pode haver menos que um subproblema

• $T(n)=64T\left({\frac {n}{8}}\right)-n^{2}\log n$

  f(n), que é o tempo de combinação (dos subproblema), não é positivo

• $T(n)=T\left({\frac {n}{2}}\right)+n(2-\cos n)$

  caso 3, mas viola a condição de regularidade.

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

Aplicação em algoritmos comuns

Algortimo	Relação de recorrência	Tempo de execução	Comentário
Pesquisa binária	$T(n)=T\left({\frac {n}{2}}\right)+O(1)$	$O(\log n)$	Aplicado o caso do teorema mestre $c=\log _{b}a$, onde $a=1,b=2,c=0,k=0$
Percurso em árvore binária	$T(n)=2T\left({\frac {n}{2}}\right)+O(1)$	$O(n)$	Aplicado o caso do teorema mestre $c<\log _{b}a$ onde$a=2,b=2,c=0$
Pesquisa ótima de matriz ordenada	$T(n)=2T\left({\frac {n}{2}}\right)+O(\log n)$	$O(n)$	Aplica o caso do método de Akra-Bazzi para $p=1$ e $g(u)=\log(u)$ $\Theta (2n-\log n)$
Merge sort	$T(n)=2T\left({\frac {n}{2}}\right)+O(n)$	$O(n\log n)$	Aplica o caso do teorema mestre $c=\log _{b}a$, onde $a=2,b=2,c=1,k=0$

Ver também

• Método de Akra-Bazzi
• Complexidade assintótica

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. ISBN 0-262-03293-7. 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. 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. 268-270.

Ligações externas

• Teorema Mestre e Exemplos Resolvidos
• Exercícios resolvidos sobre o teorema mestre