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 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.
Considere um problema que pode ser resolvido usando um algoritmo recursivo como o algoritmo a seguir: 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 {\displaystyle 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 ) {\displaystyle 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 ) {\displaystyle T(n)} , pode ser expresso pela relação de recorrência
{\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 ) = a T ( n b ) + f ( n ) {\displaystyle T(n)=aT({\frac {n}{b}})+f(n)} {\displaystyle } {\displaystyle } {\displaystyle } {\displaystyle } {\displaystyle } {\displaystyle } Aqui n {\displaystyle n} é o tamanho da entrada de um problema, a {\displaystyle a} é o número de subproblemas na recursão, e b {\displaystyle 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 ) = Θ ( 1 ) {\displaystyle T(n)=\Theta (1)} quando n {\displaystyle n} é menor que algum limite κ > 0 {\displaystyle \kappa >0} .
Exemplos
Como se pode ver a partir da fórmula acima: 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 é T ( n ) = 1001 n 3 − 1000 n 2 {\displaystyle T(n)=1001n^{3}-1000n^{2}} , assumindo T ( 1 ) = 1 {\displaystyle T(1)=1} ). T ( n ) = 2 T ( n 2 ) + 10 n {\displaystyle T(n)=2T\left({\frac {n}{2}}\right)+10n} Como podemos ver na fórmula acima as variáveis possuem os seguintes valores: Em seguida, vamos ver se conseguimos satisfazer a condição do caso 2: Do segundo caso do teorema mestre, segue que Assim, a relação de recorrência T ( n ) {\displaystyle T(n)} está em Θ ( n log n ) {\displaystyle \Theta (n\log n)} .
As equações a seguir não podem ser resolvidas utilizando o teorema mestre: No segundo exemplo inadmissível acima, a diferença entre f ( n ) {\displaystyle f(n)} e n log b a {\displaystyle n^{\log _{b}a}} pode ser expressa com a relação f ( n ) n log b a = n / log n n log 2 2 = n n log n = 1 log n {\displaystyle {\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 1 log n < n ϵ {\displaystyle {\frac {1}{\log n}}<n^{\epsilon }} para qualquer constante ϵ > 0 {\displaystyle \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 ) = Θ ( n log log n ) {\displaystyle T(n)=\Theta (n\log \log n)} .
