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 Predefinição:Math. 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)=\mathrm{\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_{\mathrm{crit}}={\log }_{b}a=\log (\mathrm{\#}\text{subproblemas})/\log (\text{tamanho relativo do subproblema})$

Caso	Descrição	Condição sobre $f(n)$ em relação a $c_{\mathrm{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_{\mathrm{crit}}$ (limitado superiormente por um polinômio de expoente menor)	... então $T(n)=\mathrm{\Theta }\left(n^{c_{\mathrm{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-ϵ})$, então $T(n)=\mathrm{\Theta }(n^{1/2})$.
2	O trabalho para dividir/recombinar um problema é comparável aos subproblemas.	Quando $f(n)=\mathrm{\Theta }(n^{c_{\mathrm{crit}}}{\log }^{k}n)$ para qualquer $k\ge 0$ (faixa limitada pelo polinômio de expoente crítico, vezes zero ou mais opcional $\log$s)	... então $T(n)=\mathrm{\Theta }\left(n^{c_{\mathrm{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)=\mathrm{\Theta }(n^{1/2})$, então $T(n)=\mathrm{\Theta }(n^{1/2}\log n)$. Se $b=a^2$ e $f(n)=\mathrm{\Theta }(n^{1/2}\log n)$, então $T(n)=\mathrm{\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)=\mathrm{\Omega }(n^c)$onde $c>c_{\mathrm{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)\le 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)=\mathrm{\Theta }(f(n))$	Se $b=a^2$ e $f(n)=\mathrm{\Omega }(n^{1/2+ϵ})$ e a condição de regularidade é satisfeita, então $T(n)=\mathrm{\Theta }(f(n))$.

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

Caso	$f(n)$ $c_{\mathrm{crit}}$, i.e. ${\log }_{b}a$	Limite do teorema mestre	Exemplos notacionais
2a	Quando $f(n)=\mathrm{\Theta }(n^{c_{\mathrm{crit}}}{\log }^{k}n)$ para qualquer $k>-1$	... então$T(n)=\mathrm{\Theta }\left(n^{c_{\mathrm{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)=\mathrm{\Theta }(n^{1/2}/{\log }^{1/2}n)$, então$T(n)=\mathrm{\Theta }(n^{1/2}{\log }^{1/2}n)$.
2b	Quando $f(n)=\mathrm{\Theta }(n^{c_{\mathrm{crit}}}{\log }^{k}n)$ fpara $k=-1$	... then $T(n)=\mathrm{\Theta }(n^{c_{\mathrm{crit}}}\log \log n)$ (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)=\mathrm{\Theta }(n^{1/2}/\log n)$, então $T(n)=\mathrm{\Theta }(n^{1/2}\log \log n)$.
2c	Quando$f(n)=\mathrm{\Theta }(n^{c_{\mathrm{crit}}}{\log }^{k}n)$ para qualquer $k<-1$	... then $T(n)=\mathrm{\Theta }\left(n^{c_{\mathrm{crit}}}\right)$ (O limite é o termo de divisão, onde o log desaparece.)	Se $b=a^2$ e$f(n)=\mathrm{\Theta }(n^{1/2}/{\log }^{2}n)$, então $T(n)=\mathrm{\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)=\mathrm{\Theta }\left(n^{{\log }_{b}a}\right)=\mathrm{\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)=\mathrm{\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)=\mathrm{\Theta }\left(n^{{\log }_{b}a}{\log }^{k+1}n\right)=\mathrm{\Theta }\left(n^1{\log }^{1}n\right)=\mathrm{\Theta }(n\log n)$

Assim, a relação de recorrência $T(n)$ está em $\mathrm{\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)=\mathrm{\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)\le k{n}^2$, escolhendo $k=1/2$

Então, pelo terceiro caso do teorema mestre:

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

Assim, a relação de recorrência $T(n)$ está em $\mathrm{\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^{ϵ}$ para qualquer constante $ϵ>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)=\mathrm{\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)$ $\mathrm{\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. Predefinição:ISBN. 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. Predefinição:ISBN. 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